# 143 Reorder List

You are given the head of a singly linked-list. The list can be represented as:
`L0 â†’ L1 â†’ â€¦ â†’ Ln - 1 â†’ Ln`
Reorder the list to be on the following form:
`L0 â†’ Ln â†’ L1 â†’ Ln - 1 â†’ L2 â†’ Ln - 2 â†’ â€¦`
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

``````1 -> 2 -> 3 -> 4
v
1 -> 4 -> 2 -> 3

Output: [1,4,2,3]
``````

Example 2:

``````1 -> 2 -> 3 -> 4 -> 5
v
1 -> 5 -> 2 -> 4 -> 3

• The number of nodes in the list is in the range `[1, 5 * 104]`.
• `1 <= Node.val <= 1000`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 `````` ``````class Solution: def reorderList(self, head: ListNode) -> None: if not head: return # find the middle of linked list [Problem 876] # in 1->2->3->4->5->6 find 4 slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # reverse the second part of the list [Problem 206] # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4 # reverse the second half in-place prev, curr = None, slow while curr: curr.next, prev, curr = prev, curr, curr.next # merge two sorted linked lists [Problem 21] # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4 first, second = head, prev while second.next: first.next, first = second, first.next second.next, second = first, second.next ''' Using recursion ''' # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reorderList(self, head: Optional[ListNode]) -> None: """ Do not return anything, modify head in-place instead. """ prev = slow = fast = head while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next prev.next = None last, rev_head = self.reverseList(slow) last.next = None self.mergeList(head, rev_head) def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None, None if not head.next: return head, head last, new_head = self.reverseList(head.next) last.next = head return head, new_head def mergeList( self, l1: Optional[ListNode], l2: Optional[ListNode] ) -> Optional[ListNode]: if not l1: return l2 if not l2: return l1 l1.next, l2.next = l2, self.mergeList(l1.next, l2.next) return l1``````