Reorder List

Q: Why reverse the second half of the list?

The answer reads the back half from its last node to its first, and a singly linked list only walks forward. Reversing the back half once, in O(n) , lets the merge walk both halves forward.

Q: What is the time complexity of Reorder List?

The in place method runs in O(n) time with O(1) extra memory: finding the middle, reversing and weaving each visit every node a constant number of times. Copying the values into an array is also O(n) time but needs O(n) memory, and moving the tail forward one node at a time is O(n²) .

Q: Where is the middle when the list has an even number of nodes?

Stop the slow pointer on the last node of the front half. With six nodes the halves are three and three; with five they are three and two. The extra node then ends the answer, which is where the order puts the middle value.

MediumLinked list Fast and slow pointers Two pointers

+10

You get a singly linked list stored in two arrays of the same length. Node i holds the value values[i] and links to node next[i], -1 ends the list, and the head is node 0. The nodes are not stored in list order, so follow the links.

Call the nodes in list order L0, L1, ..., Lk. Reorder the list so it runs L0, Lk, L1, Lk-1, L2, Lk-2, ...: the first node, then the last, then the second, then the second to last, and so on. Return the values in that new order.

Function

reorderList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: the index of the node each node links to, or -1 for the last node
valuesinteger-array: the value held by each node
Returnsinteger-array: the values in the reordered list order

Constraints

1 ≤ n ≤ 4000, where n is the length of next and of values.
-1000 ≤ values[i] ≤ 1000
Each next[i] is -1 or a node index from 0 to n-1.
Starting at node 0, the list visits every node exactly once and then reaches -1. There is no cycle.

Examples

Input: next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
Output: [1, 5, 2, 4, 3]
Explanation: Following the links from node 0, the list reads 1, 2, 3, 4, 5. First, last, second and second to last give 1, 5, 2, 4, and the middle value 3 comes last.

Input: next = [2, 3, 1, -1]values = [10, 30, 20, 40]
Output: [10, 40, 20, 30]
Explanation: The list visits nodes 0, 2, 1, 3 and reads 10, 20, 30, 40. First and last give 10, 40, then the inner pair gives 20, 30.

Input: next = [-1]values = [7]
Output: [7]
Explanation: A list with one node has nothing to move, so the answer is [7].

Follow-up

Can you reorder the links themselves with O(1) extra memory?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The new order alternates between the front and the back, but a singly linked list only walks forward. Split the job into three standard list moves: find the middle with slow and fast pointers, reverse the back half, and weave the two halves together one node at a time.

Move the tail forward, one node at a time

Intuition

A pointer here is a node index, and moving forward is node = next[node]. After the first node comes the last, so unhook the last node and insert it after the current one, then repeat two nodes further on. For 1, 2, 3, 4, 5 that gives 1, 5, 2, 3, 4, then 1, 5, 2, 4, 3. Stop when fewer than two nodes follow the current one.

Finding the node before the last takes a walk to the end every round. The walks shrink by two nodes a round, about n²/4 moves in total: four million for 4000 nodes.

Algorithm

Set cur = 0.
While at least two nodes follow cur, walk before from cur until next[next[before]] == -1, so tail = next[before] is the last node.
Unhook it with next[before] = -1, then insert it: next[tail] = next[cur] and next[cur] = tail.
Move cur to next[tail] and repeat.
Walk from node 0 and collect the values.

def reorderList(next, values):
    cur = 0
    # While at least two nodes follow cur, move the last node right after cur.
    while next[cur] != -1 and next[next[cur]] != -1:
        before = cur
        while next[next[before]] != -1:  # find the node before the tail
            before = next[before]
        tail = next[before]
        next[before] = -1
        next[tail] = next[cur]
        next[cur] = tail
        cur = next[tail]
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Copy the values and read from both ends

Intuition

An array reaches its last element in one step. Copy the values in list order, [1, 2, 3, 4, 5] in the first example, then read with lo from the front and hi from the back: take lo, take hi, and move both inward while lo < hi. That gives 1, 5, 2, 4; with an odd length both meet on the middle 3, which goes last.

That is O(n) time and O(n) extra memory, and the links never change.

Algorithm

Walk from node 0 and append each value to inOrder.
Set lo = 0 and hi to the last index.
While lo < hi, append inOrder[lo] and inOrder[hi], then move lo up and hi down.
If lo == hi, append the middle value.

def reorderList(next, values):
    # Write the values out in list order.
    in_order = []
    node = 0
    while node != -1:
        in_order.append(values[node])
        node = next[node]
    # Take from the front and the back in turn.
    result = []
    lo, hi = 0, len(in_order) - 1
    while lo < hi:
        result.append(in_order[lo])
        result.append(in_order[hi])
        lo += 1
        hi -= 1
    if lo == hi:  # odd length: the middle value comes last
        result.append(in_order[lo])
    return result

Find the middle, reverse the back half, weave

Intuition

For 1, 2, 3, 4, 5, 6 the answer is 1, 6, 2, 5, 3, 4: the front half 1, 2, 3 in order, alternating with the back half 4, 5, 6 read backwards. So cut the list at the middle, reverse the back half, and weave.

slow moves one link while fast moves two, so slow stops on the last node of the front half: the 3, for both five and six nodes. Cutting after it gives the front half the extra node when the length is odd, and that node ends the answer. The weave takes one node from each half in turn until the back half runs out.

Every node is touched a constant number of times, with a few indexes of memory. R copies the link vector on its first change, so in R the memory is O(n).

Algorithm

Move slow one link and fast two links while next[fast] and next[next[fast]] are not -1.
Set second = next[slow], then next[slow] = -1.
Reverse the list that starts at second; its new head is prev.
Weave: while second is not -1, link first to second and second to the old next[first], then advance both.
Walk from node 0 and collect the values.

def reorderList(next, values):
    # 1. Find the middle: slow stops on the last node of the first half.
    slow = fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    second = next[slow]
    next[slow] = -1  # cut the list in two
    # 2. Reverse the second half.
    prev = -1
    while second != -1:
        after = next[second]
        next[second] = prev
        prev = second
        second = after
    # 3. Weave: one node from the front half, one from the reversed back half.
    first, second = 0, prev
    while second != -1:
        first_after, second_after = next[first], next[second]
        next[first] = second
        next[second] = first_after
        first, second = first_after, second_after
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pitfalls and edge cases

Not cutting the list after the middle. Without next[slow] = -1, the front half still points into the back half, and after the weave the list loops back on itself.
Overwriting a link before saving it. In the reversal and the weave, read next[node] into a variable first, or the rest of the list is lost.
Weaving until the front half ends. With an odd length that loop runs once more with second at -1 and reads next[-1].
Reading the array order as the list order. In the first example values is [1, 3, 5, 2, 4], but the list reads 1, 2, 3, 4, 5.
In Lua and R arrays start at 1. Keep node indexes 0-based and read next[node + 1].

Frequently asked questions3

Why reverse the second half of the list?

The answer reads the back half from its last node to its first, and a singly linked list only walks forward. Reversing the back half once, in O(n), lets the merge walk both halves forward.

What is the time complexity of Reorder List?

The in place method runs in O(n) time with O(1) extra memory: finding the middle, reversing and weaving each visit every node a constant number of times. Copying the values into an array is also O(n) time but needs O(n) memory, and moving the tail forward one node at a time is O(n²).

Where is the middle when the list has an even number of nodes?

Stop the slow pointer on the last node of the front half. With six nodes the halves are three and three; with five they are three and two. The extra node then ends the answer, which is where the order puts the middle value.

def reorderList(next, values):
    # Write code here

Test #1

Test #2

Test #3

Arguments

next = [3, 4, -1, 1, 2]
values = [1, 3, 5, 2, 4]

Expected Output

[1, 5, 2, 4, 3]

Reorder List

Function

Constraints

Examples

Hints

Solution

Move the tail forward, one node at a time

Copy the values and read from both ends

Find the middle, reverse the back half, weave

Pitfalls and edge cases

Frequently asked questions3

Similar problems