You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → L2 → ... → Ln-1 → Ln
Reorder the list to be in 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.
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Pattern Recognition: Take nodes from both ends alternately.
For 1 → 2 → 3 → 4 → 5:
1 → 5 → 2 → 4 → 3Key Challenge: Can't access end of linked list easily.
Solution: Break into 3 steps:
This is a Linked List Manipulation problem combining:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# slow is now at middle
prev, curr = None, slow
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
# prev is new head of reversed second half
first, second = head, prev
while second.next:
temp1, temp2 = first.next, second.next
first.next = second
second.next = temp1
first, second = temp1, temp2
Time: O(n)
Space: O(1)
For 1 → 2 → 3 → 4 → 5:
Phase 1 - Find Middle:
slow: 1 → 2 → 3
fast: 1 → 3 → 5 → null
Middle found at 3
Phase 2 - Reverse Second Half:
Original: 3 → 4 → 5
Reversed: 5 → 4 → 3
Phase 3 - Merge:
First: 1 → 2 → 3
Second: 5 → 4 → 3
Merge: 1 → 5 → 2 → 4 → 3
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode() {}
7 * ListNode(int val) { this.val = val; }
8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11
12class Solution {
13 public void reorderList(ListNode head) {
14 if (head == null || head.next == null) {
15 return;
16 }
17
18 // Step 1: Find middle using slow/fast pointers
19 ListNode slow = head;
20 ListNode fast = head;
21
22 while (fast != null && fast.next != null) {
23 slow = slow.next;
24 fast = fast.next.next;
25 }
26
27 // Step 2: Reverse second half
28 ListNode prev = null;
29 ListNode curr = slow;
30
31 while (curr != null) {
32 ListNode nextTemp = curr.next;
33 curr.next = prev;
34 prev = curr;
35 curr = nextTemp;
36 }
37
38 // Step 3: Merge two halves alternately
39 ListNode first = head;
40 ListNode second = prev;
41
42 while (second.next != null) {
43 // Save next pointers
44 ListNode temp1 = first.next;
45 ListNode temp2 = second.next;
46
47 // Rewire connections
48 first.next = second;
49 second.next = temp1;
50
51 // Move to next pair
52 first = temp1;
53 second = temp2;
54 }
55 }
56}
57
58
59// Alternative Solution: Using Stack (Less Optimal - O(n) space)
60class SolutionStack {
61 public void reorderList(ListNode head) {
62 if (head == null || head.next == null) {
63 return;
64 }
65
66 // Push all nodes to stack
67 Stack<ListNode> stack = new Stack<>();
68 ListNode curr = head;
69 while (curr != null) {
70 stack.push(curr);
71 curr = curr.next;
72 }
73
74 // Merge from start and end
75 curr = head;
76 int count = stack.size() / 2;
77
78 for (int i = 0; i < count; i++) {
79 // Get node from end
80 ListNode endNode = stack.pop();
81
82 // Insert after current
83 ListNode nextNode = curr.next;
84 curr.next = endNode;
85 endNode.next = nextNode;
86
87 // Move to next position
88 curr = nextNode;
89 }
90
91 // Terminate list
92 curr.next = null;
93 }
94}
95
96
97// Alternative Solution: Using ArrayList
98class SolutionArrayList {
99 public void reorderList(ListNode head) {
100 if (head == null || head.next == null) {
101 return;
102 }
103
104 // Store all nodes in ArrayList
105 List<ListNode> nodes = new ArrayList<>();
106 ListNode curr = head;
107 while (curr != null) {
108 nodes.add(curr);
109 curr = curr.next;
110 }
111
112 // Reorder using two pointers on ArrayList
113 int left = 0;
114 int right = nodes.size() - 1;
115 ListNode dummy = new ListNode(0);
116 curr = dummy;
117
118 while (left <= right) {
119 // Add from left
120 curr.next = nodes.get(left);
121 curr = curr.next;
122 left++;
123
124 // Add from right (if exists)
125 if (left <= right) {
126 curr.next = nodes.get(right);
127 curr = curr.next;
128 right--;
129 }
130 }
131
132 // Terminate list
133 curr.next = null;
134 }
135}
136