You are given the head of a singly linked list L0 -> L1 -> ... -> Ln. Rearrange it in place into the order L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ..., alternating one node from the front with one node from the back. You must move nodes, not just swap their values. The function returns nothing.
- 1 <= number of nodes <= 5 * 10^4
- 1 <= Node.val <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force stores all nodes in an array and links them with two pointers from both ends: O(n) time and O(n) extra space. Notice that the answer interleaves the first half with the reversed second half. Every piece of that is a standard linked list routine: slow/fast pointers find the middle, an in-place reversal flips the second half, and a simple merge alternates nodes. All three run in O(n) time with O(1) extra space.
Algorithm
- Use
slowandfastpointers to find the end of the first half. - Cut the list after
slowand reverse the second half. - Merge: take one node from the first half, then one from the reversed second half, and repeat.
- Stop when the second half runs out; the first half may have one extra node, which stays at the end.
O(n)Space: O(1)slow.next = null) before reversing creates a cycle, which usually shows up as a time limit exceeded error. Interviewers like this problem because it tests three linked list patterns at once.class Solution: def reorderList(self, head: Optional[ListNode]) -> None: if not head or not head.next: return # 1. Find the end of the first half. slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # 2. Cut and reverse the second half. second = slow.next slow.next = None prev = None while second: nxt = second.next second.next = prev prev = second second = nxt # 3. Merge the halves alternately. first, second = head, prev while second: n1, n2 = first.next, second.next first.next = second second.next = n1 first, second = n1, n2