Reorder List

2 min read
LC-Medium
Linked List

Oct 21, 2022

3 years ago

LeetCode

Solution

Split the list in two, using the same concepts as Middle of Linked List
- In the case of odd number of nodes, first half would have the greater number of nodes
Now, reverse the second half of the list, using the same concepts as Reverse A Linked List
Now, alternate between the two lists and change the links between them, BUT: KEEP IN MIND:
- After reversing the second list, set the slow.next to None, because this will get rid of the existing link between the last node of the first linked list. If you don't do this there will be a cycle in the linked list
- Then, alternate through both the lists and change the links using temporary nodes.
  - During this traversal, the condition for the while loop can be while second because the second linked list would be the shorter of the two. In the case where both are equal, it doesn't matter and it would correctly terminate the while loop
Here is the logic for alternating:

first, second = head, prev while second: t1, t2 = first.next, second.next first.next = second second.next = t1 first, second = t1, t2

Time	Space	Explanation
`O(n)`	`O(1)`

def reorderList(self, head: Optional[ListNode]) -> None: # find middle of list slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # reverse 2nd half of list prev, curr = None, slow.next while curr: next = curr.next curr.next = prev prev = curr curr = next slow.next = None # Remove link from last node of first list so that cycle doesn't occur # Alternate between lists and change links first, second = head, prev while second: # This is valid because the second list would be the shorter of the two lists t1, t2 = first.next, second.next first.next = second second.next = t1 first, second = t1, t2