The challenge
Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … in place.
Change links rather than values; the input is acyclic.
Example
[1, 2, 3, 4, 5] → [1, 5, 2, 4, 3].
Use the walkthrough below to inspect the input and each state change.
See Reorder list, step by step
Follow the pointers. Watch each link change.
5 nodes · singly linkedIDs = node identity · ∅ = null
CurrentResultYellow arrow: changed next link
head
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 2 | A3 |
| A3 | 3 | A4 |
| A4 | 4 | A5 |
| A5 | 5 | null |
Step 01 / 13
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 2 (A2) → 3 (A3) → 4 (A4) → 5 (A5); parameters: {}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Reversing the second half makes the next end node available at its head.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prev
def reorder(head):
if head is None or head.next is None:
return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second = reverse(slow.next)
slow.next = None
first = head
while second:
next_first, next_second = first.next, second.next
first.next = second
second.next = next_first
first, second = next_first, next_second
return head
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* reverse(Node* head) {
Node* prev = nullptr;
while (head) {
Node* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
Node* reorder(Node* head) {
if (!head || !head->next) return head;
Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
Node* second = reverse(slow->next);
slow->next = nullptr;
Node* first = head;
while (second) {
Node* next_first = first->next;
Node* next_second = second->next;
first->next = second;
second->next = next_first;
first = next_first;
second = next_second;
}
return head;
}