Reorder List

The problem

You are given the head of a singly linked list with nodes L0, L1, …, Ln−1. Reorder it to:

L0, Ln−1, L1, Ln−2, L2, …

So the first node, then the last, then the second, then the second to last, and so on. Change the links between nodes, not the values inside them. Return nothing: change the list in place.

Example 1

Input: head = [10, 20, 30, 40, 50, 60]

Output: [10, 60, 20, 50, 30, 40]

Front and back take turns. The top row is the first half, the bottom row is the second half.

Example 2

Input: head = [7, 3, 9, 1, 5]

Output: [7, 5, 3, 1, 9]

With an odd count, the middle node, 9, ends up last.

Example 3

Input: head = [4]

Output: [4]

One node has nothing to reorder.

Constraints

• 1 ≤ n ≤ 50,000, where n is the number of nodes
• 1 ≤ Node.val ≤ 1,000

Clarifying questions

May we just swap the values?

No. The nodes themselves must move, by changing their next pointers.

Do we return a new head?

No. The head stays the same node, so the function returns nothing.

Can the list be empty?

No, it has at least one node. One or two nodes are already in order.

Is extra memory allowed?

An array of the nodes works. The best answer uses only a few pointers.

Spot the pattern

The order needs nodes from both ends at once, but a singly linked list only walks forward. Two tricks fix that. Fast and slow pointers find the middle in one pass. Reversing the second half makes its last node come first. After that it is a plain merge of two lists, taking turns.

Solutions

Array of nodesO(n), O(n) spaceSplit, reverse, weaveO(n), O(1) space

Show all

A slower way with no extra memory walks to the end of the list for every node, which is O(n²). The array below is the simple version worth knowing.

Array of nodes O(n), O(n) space

The idea

The hard part is reaching the back of the list. So copy every node into an array. Now index j reaches any node from the back in one step.

Put i at the front and j at the back. Link nodes[i] to nodes[j], then nodes[j] to nodes[i + 1], and move both inward. When they meet, that node is the new tail. Set its next to null, or the list would loop.

Walkthrough

nodes

100201302403504605

ij

1. nodes = [every node, in order]
2. i, j = 0, len(nodes) - 1
3. while i < j:
4. nodes[i].next = nodes[j]
5. i += 1
6. if i == j: break
7. nodes[j].next = nodes[i]
8. j -= 1
9. nodes[i].next = None

Copy every node into an array. Now any node can be reached by its index in one step, from either end.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Array of nodes: index j reaches the back in one step. Link front and back
    // in turns. O(n) time, but the array costs O(n) memory.
    public void reorderList(ListNode head) {
        java.util.List<ListNode> nodes = new java.util.ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) nodes.add(node);
        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i == j) break;
            nodes.get(j).next = nodes.get(i);
            j--;
        }
        // The meeting node is the new tail. Cut its old link, or the list loops.
        nodes.get(i).next = null;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. Copying adds one node to the array per run. The linking loop sets one next pointer and moves one index per link. Each of those is 1 step.

   1. nodes = [every node, in order]
   2. i, j = 0, len(nodes) - 1
   3. while i < j:
   4. nodes[i].next = nodes[j]
   5. i += 1
   6. if i == j: break
   7. nodes[j].next = nodes[i]
   8. j -= 1
   9. nodes[i].next = None

2. 2 Count the runs on Example 1

   Example 1 has 6 nodes. Copying takes 6 runs. Linking makes 5 links: 10 to 60, 60 to 20, 20 to 50, 50 to 30 and 30 to 40.

   6 + 5 = 11 steps.

   part	copy nodes	link
   runs	6	5

   total

   6 + 5 = 11

3. 3 Write the count for any n

   The copy touches each node once. Each link moves i or j one step closer, and they start n − 1 apart:

   n + (n − 1) = 2n − 1

   Check it with Example 1: 2 × 6 − 1 = 11.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The array holds a reference to every node, so n slots. The space is O(n).

   nodes (n slots)ij

Split, reverse, weave O(n), O(1) space

The idea

Do the job in three steps, with no array.

1. Find the middle. Move slow 1 node and fast 2 nodes per run. When fast cannot go 2 more, slow is at the end of the first half. Cut the list after it.
2. Reverse the second half. Now its last node comes first, which is the order we need.
3. Weave. Take one node from the first half, then one from the reversed second half, and repeat.

Why it is correct: after step 2, the second half lists Ln−1, Ln−2, … in that order. Weaving it with L0, L1, … gives exactly L0, Ln−1, L1, Ln−2, …. The first half is never shorter, so no node is left behind.

Walkthrough

1. slow = fast = head
2. while fast.next and fast.next.next:
3. slow, fast = slow.next, fast.next.next
4. second, slow.next = slow.next, None
5. previous = None
6. while second:
7. second.next, previous, second = previous, second, second.next
8. first, second = head, previous
9. while second:
10. first_next, second_next = first.next, second.next
11. first.next, second.next = second, first_next
12. first, second = first_next, second_next

Step 1: find the middle. slow moves 1 node per run and fast moves 2, so slow stops halfway.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Split, reverse, weave: find the middle, reverse the second half, then
    // take one node from each half in turn. O(n) time and O(1) memory.
    public void reorderList(ListNode head) {
        // fast moves 2 per run, so slow stops at the end of the first half.
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // Cut the halves apart, or the weave would make a loop.
        ListNode second = slow.next;
        slow.next = null;
        // Reverse the second half, so its last node comes first.
        ListNode previous = null;
        while (second != null) {
            ListNode nextNode = second.next;
            second.next = previous;
            previous = second;
            second = nextNode;
        }
        // The first half is never shorter, so stop when the second runs out.
        ListNode first = head;
        second = previous;
        while (second != null) {
            ListNode firstNext = first.next, secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are three loops, one after the other. Each run of each loop moves a few pointers, which is 1 step. None of them sits inside another.

   1. slow = fast = head
   2. while fast.next and fast.next.next:
   3. slow, fast = slow.next, fast.next.next
   4. second, slow.next = slow.next, None
   5. previous = None
   6. while second:
   7. second.next, previous, second = previous, second, second.next
   8. first, second = head, previous
   9. while second:
   10. first_next, second_next = first.next, second.next
   11. first.next, second.next = second, first_next
   12. first, second = first_next, second_next

2. 2 Count the runs on Example 1

   Example 1 has 6 nodes. Finding the middle takes 2 runs. Reversing the 3 nodes of the second half takes 3 runs. Weaving those 3 nodes into the first half takes 3 runs.

   2 + 3 + 3 = 8 runs.

   loop	find middle	reverse	weave
   runs	2	3	3

   total

   2 + 3 + 3 = 8

3. 3 Write the count for any n

   Fast moves 2 nodes per run, so finding the middle takes about n / 2 runs. The second half has about n / 2 nodes, and both the reverse and the weave touch each of them once:

   about n/2 + n/2 + n/2 = 3n/2

   Check it with Example 1: 3 × 6 / 2 = 9, and the real count is 8 because the middle search stops one run early.

4. 4 Keep only the part that grows fastest

   Drop the 3/2. Three half-passes do not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps a handful of pointers: slow, fast, previous, first, second, first_next and second_next. That is fixed, for any n, so the space is O(1).

   slowfastpreviousfirstsecondfirst_nextsecond_next

Common mistake

Not cutting the list in the middle

If you forget slow.next = None, the first half still links into the second. After the weave, the last node points back into the list and makes a loop. Cut first, then reverse.

Tested at the limits

2,000 random lists of 1 to 9 nodes, with odd and even lengths and single nodes. The array of nodes and split, reverse, weave gave the same order every time, and it matched a simple check that takes from the front and the back in turns.

Largest inputs	Result
50,000 nodes (the most allowed). Split, reverse, weave.	0.002 s, and under 0.001 MB of extra memory: a few pointers, whatever the length.
50,000 nodes, the same list. Array of nodes.	0.003 s, and about 0.4 MB of extra memory: the array holds every node, which is the O(n) space.