Log inSign up
mediumLeetCodeNot Started

Reorder List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:

L0 -> L1 -> ... -> Ln - 1 -> Ln

Reorder the list to be on 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.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]
Explanation: Original order: 1 -> 2 -> 3 -> 4. Interleaved with reversed second half (4 -> 3): 1 -> 4 -> 2 -> 3.

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: First half: [1, 2, 3]. Reversed second half: [5, 4]. Interleaved: 1 -> 5 -> 2 -> 4 -> 3.

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 1000

1. Array Node Storage & Two-Pointer Linking

Intuition

1. Traverse list and store node references in an array nodes. 2. Use two indices i = 0 and j = nodes.length - 1. 3. While i < j: - nodes[i].next = nodes[j] - i++ - If i == j, break. - nodes[j].next = nodes[i] - j-- 4. Terminate with nodes[i].next = null.

When to apply: Quick solution when extra O(N) memory is acceptable.

Algorithm

  1. Collect all nodes into a vector/array.
  2. Run two pointers from ends towards center.
  3. Wire alternating next pointers.
  4. Set last center node's next to null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14 void reorderList(ListNode* head) {
15 if (!head || !head->next) return;
16
17 std::vector<ListNode*> nodes;
18 ListNode* curr = head;
19 while (curr != nullptr) {
20 nodes.push_back(curr);
21 curr = curr->next;
22 }
23
24 int i = 0, j = nodes.size() - 1;
25 while (i < j) {
26 nodes[i]->next = nodes[j];
27 i++;
28 if (i >= j) break;
29 nodes[j]->next = nodes[i];
30 j--;
31 }
32 nodes[i]->next = nullptr;
33 }
34};
35
36int main() {
37 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
38 Solution sol;
39 sol.reorderList(head);
40 ListNode* curr = head;
41 while (curr != nullptr) {
42 std::cout << curr->val << " ";
43 curr = curr->next;
44 }
45 std::cout << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N) — One pass to populate the array (N steps) and one pass of two-pointer rewiring (N steps): O(N) overall.
  • Space complexity: O(N) — O(N) memory to store references to all N nodes in an array.

2. Deque (Double-Ended Queue) Node Simulation

Intuition

1. Push all list nodes into a deque dq. 2. Set curr = dq.popleft(). 3. While dq is not empty: - If deque is non-empty, pop from back nodeBack = dq.pop() and attach curr.next = nodeBack; curr = curr.next. - If deque is non-empty, pop from front nodeFront = dq.popleft() and attach curr.next = nodeFront; curr = curr.next. 4. Set curr.next = null.

When to apply: When demonstrating queue/stack data structure integration with list nodes.

Algorithm

  1. Push nodes into double-ended queue.
  2. Pop alternatively from head and tail.
  3. Re-link next pointers sequentially.
  4. Set terminal next pointer to null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <deque>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14 void reorderList(ListNode* head) {
15 if (!head || !head->next) return;
16
17 std::deque<ListNode*> dq;
18 ListNode* curr = head->next;
19 while (curr != nullptr) {
20 dq.push_back(curr);
21 curr = curr->next;
22 }
23
24 curr = head;
25 bool takeBack = true;
26 while (!dq.empty()) {
27 if (takeBack) {
28 curr->next = dq.back();
29 dq.pop_back();
30 } else {
31 curr->next = dq.front();
32 dq.pop_front();
33 }
34 curr = curr->next;
35 takeBack = !takeBack;
36 }
37 curr->next = nullptr;
38 }
39};
40
41int main() {
42 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
43 Solution sol;
44 sol.reorderList(head);
45 ListNode* curr = head;
46 while (curr != nullptr) {
47 std::cout << curr->val << " ";
48 curr = curr->next;
49 }
50 std::cout << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N) — Each node is inserted and removed from the deque in O(1) time, giving O(N) overall.
  • Space complexity: O(N) — Deque holds references to all N nodes in memory: O(N) space.

3. In-Place 3-Stage: Find Mid, Reverse 2nd Half, Interleave

Intuition

1. Find mid: Use slow and fast pointers. slow stops at midpoint; split list into two by setting slow.next = null after saving head of second half. 2. Reverse second half: Using 3-pointer standard iterative reversal (prev, curr, next), reverse the second half. 3. Interleave: Maintain pointers first (start of 1st half) and second (start of reversed 2nd half). Alternate first.next = second and second.next = tmpFirst until exhaustion.

When to apply: The definitive, O(1) memory industry-standard solution tested in FAANG coding interviews.

Algorithm

  1. Find middle with fast/slow pointers.
  2. Split list into two distinct chains.
  3. Reverse second chain in-place.
  4. Interleave nodes from first and second chains.
  5. Terminate cleanly with O(1) extra space.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
List is split into First Half: [1 -> 2] and Second Half: [3 -> 4]
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

List is split into First Half: [1 -> 2] and Second Half: [3 -> 4].

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 void reorderList(ListNode* head) {
14 if (!head || !head->next) return;
15
16 // Step 1: Find middle using Slow & Fast pointers
17 ListNode* slow = head;
18 ListNode* fast = head;
19 while (fast->next != nullptr && fast->next->next != nullptr) {
20 slow = slow->next;
21 fast = fast->next->next;
22 }
23
24 // Step 2: Reverse second half
25 ListNode* second = slow->next;
26 slow->next = nullptr; // disconnect first half
27
28 ListNode* prev = nullptr;
29 ListNode* curr = second;
30 while (curr != nullptr) {
31 ListNode* nextTemp = curr->next;
32 curr->next = prev;
33 prev = curr;
34 curr = nextTemp;
35 }
36 second = prev; // head of reversed second half
37
38 // Step 3: Interleave first and second halves
39 ListNode* first = head;
40 while (second != nullptr) {
41 ListNode* tmp1 = first->next;
42 ListNode* tmp2 = second->next;
43
44 first->next = second;
45 second->next = tmp1;
46
47 first = tmp1;
48 second = tmp2;
49 }
50 }
51};
52
53int main() {
54 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
55 Solution sol;
56 sol.reorderList(head);
57 ListNode* curr = head;
58 while (curr != nullptr) {
59 std::cout << curr->val << " ";
60 curr = curr->next;
61 }
62 std::cout << std::endl;
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(N) — Finding middle is N/2 steps, reversing second half is N/2 steps, merging is N steps. Total time is 2N = O(N).
  • Space complexity: O(1) auxiliary — All operations modify existing next pointers in-place without auxiliary data structures: O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array Node Storage & Two-Pointer LinkingO(N)O(N)Store pointers to all nodes in a flat array, then use two pointers i = 0 and j = n - 1 to rewire the next pointers alternating between left and right ends.High time complexity
2.Deque (Double-Ended Queue) Node SimulationO(N)O(N)Push all nodes into a double-ended queue. Repeatedly pop from front and back to construct the reordered sequence.—
3.In-Place 3-Stage: Find Mid, Reverse 2nd Half, InterleaveOptimalO(N)O(1) auxiliary1. Find middle of list using fast/slow pointers. 2. Reverse the second half in-place. 3. Weave the first half and reversed second half together with alternating pointers in O(1) auxiliary space.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Failing to sever the link between first half and second half (slow.next = null), causing endless circular reference cycles during interleaving.

Pitfall 2:

Off-by-one mid detection: using while (fast != null && fast.next != null) makes slow land on the second middle in even-length lists, causing asymmetry.

Pitfall 3:

Losing references when interleaving without caching first.next and second.next.

Back to DSA Sheet