You are given the head of a singly linked list. Reorder it such that the nodes are arranged in
the pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
You may not modify the values in the list's nodes; only node links may be changed.
Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]
Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
The solution uses three steps:
- Step 1 - Find the middle: Use slow/fast pointers to split the list into two halves.
- Step 2 - Reverse the second half: Reverse the second half in-place so that traversing from the end becomes possible in O(1) space.
- Step 3 - Merge the two halves: Interleave nodes from the first half and the reversed second half alternately.
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class ReorderList {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Step 1: Find middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse second half
ListNode second = slow.next;
slow.next = null; // cut the list
ListNode prev = null;
ListNode curr = second;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
second = prev; // second now points to reversed second half
// Step 3: Interleave the two halves
ListNode first = head;
while (second != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
}
Complexity Analysis:
Time complexity: O(n) — each of the three steps (find middle, reverse, merge) takes O(n/2).
Space complexity: O(1) as the reordering is done in-place with a constant number of pointers.