Reorder a Linked List
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in head ≤ 200 - ◆
-1000 ≤ node value ≤ 1000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node reorderList(Node head) { |
| 3 | if (head == null || head.next == null) { |
| 4 | return head; |
| 5 | } |
| 6 | Node slow = head, fast = head; |
| 7 | while (fast.next != null && fast.next.next != null) { |
| 8 | slow = slow.next; |
| 9 | fast = fast.next.next; |
| 10 | } |
| 11 | Node secondHead = slow.next; |
| 12 | slow.next = null; |
| 13 | Node prev = null; |
| 14 | Node curr = secondHead; |
| 15 | while (curr != null) { |
| 16 | Node nextNode = curr.next; |
| 17 | curr.next = prev; |
| 18 | prev = curr; |
| 19 | curr = nextNode; |
| 20 | } |
| 21 | secondHead = prev; |
| 22 | Node first = head; |
| 23 | Node second = secondHead; |
| 24 | while (second != null) { |
| 25 | Node firstNext = first.next; |
| 26 | Node secondNext = second.next; |
| 27 | first.next = second; |
| 28 | if (firstNext != null) { |
| 29 | second.next = firstNext; |
| 30 | } |
| 31 | first = firstNext; |
| 32 | second = secondNext; |
| 33 | } |
| 34 | return head; |
| 35 | } |
| 36 | } |
| 37 |
1More than one node — reordering actually needs to happen.
Approach & Solutions
Brute Force — Collect Nodes Into an Array, Reorder by Index
GoodCopy every value into an array, then build the reordered sequence by alternately taking from the front and the back of that array. Walk the list once more overwriting .val in that new order. Simple and correct, but it costs an array (twice over, really) the size of the whole list — the optimal solution reorders in place with no extra memory.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node reorderList(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 List<Integer> reordered = new ArrayList<>();
16 int lo = 0, hi = vals.size() - 1;
17 while (lo <= hi) {
18 reordered.add(vals.get(lo));
19 lo++;
20 if (lo <= hi) {
21 reordered.add(vals.get(hi));
22 hi--;
23 }
24 }
25 curr = head;
26 for (int v : reordered) {
27 curr.val = v;
28 curr = curr.next;
29 }
30 return head;
31 }
32}Optimal — Split, Reverse the Second Half, Merge Alternately
OptimalFind the end of the first half with slow/fast pointers, then cut the list into two independent halves right there. Reverse the second half in place — the exact same relink primitive used to reverse any run of nodes. What's left is two ordinary lists of (almost) equal length, one running forward from the original front and one running "backward" from the original end. Merge them by strictly alternating one node from each — first, second, first, second — which produces L0, Ln, L1, Ln-1, ... automatically, with no new nodes.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node reorderList(Node head) {
9 if (head == null || head.next == null) {
10 return head;
11 }
12 Node slow = head, fast = head;
13 while (fast.next != null && fast.next.next != null) {
14 slow = slow.next;
15 fast = fast.next.next;
16 }
17 Node secondHead = slow.next;
18 slow.next = null;
19 Node prev = null;
20 Node curr = secondHead;
21 while (curr != null) {
22 Node nextNode = curr.next;
23 curr.next = prev;
24 prev = curr;
25 curr = nextNode;
26 }
27 secondHead = prev;
28 Node first = head;
29 Node second = secondHead;
30 while (second != null) {
31 Node firstNext = first.next;
32 Node secondNext = second.next;
33 first.next = second;
34 if (firstNext != null) {
35 second.next = firstNext;
36 }
37 first = firstNext;
38 second = secondNext;
39 }
40 return head;
41 }
42}