Start learning free

LESSON 378 OF 540 · LINKED LISTS

Reorder List in Go: Middle, Reverse and Merge in O(n), O(1)

Practice O(n) Read the full explanation

You are given the head of a singly linked list. Its nodes, in order, are:

L0 -> L1 -> L2 -> ... -> Ln-2 -> Ln-1 -> Ln

Reorder the list so that it becomes:

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

That is: the first node, then the last, then the second, then the second to last, and so on, until every node is used once.

Change only the links between the nodes: don't change the values inside them and don't create new nodes. The function returns nothing. It reorders the list in place, the list still starts at head, and the list is printed from there.

 

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]
Explanation: The first node, 1, stays first. The last node, 4, comes next,
then the second node, 2, and the second to last, 3:
1->4->2->3

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: 1 and 5 (first and last), then 2 and 4 (second and second to last).
The middle node, 3, is left over and ends the list:
1->5->2->4->3

Example 3:

Input: head = [4,8]
Output: [4,8]
Explanation: With two nodes, the last node already comes right after the first:
nothing moves.

 

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000
  • Values can repeat.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the number of nodes: it only re-links the nodes that are already there. Copying the nodes into an array first would take O(n) extra space.

It takes three passes over the list:

  1. Find the middle with two pointers, a slow one that moves one node at a time and a fast one that moves two, and cut the list after the middle: 1->2->3->4->5 becomes 1->2->3 and 4->5.
  2. Reverse the second half, as in Reverse Linked List: 4->5 becomes 5->4.
  3. Take nodes from the two halves in turn: 1->5->2->4->3.
STEP 1 OF 18
    Ctrl + Enter to check

    GO · LINKED LISTS

    Reorder List in Go, explained

    Problem overview

    The function reorderList gets head, a pointer to the first ListNode of a singly linked list with at least one node (the lesson provides ListNode, with a Val and a Next pointer). It must rearrange the nodes from L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: the first node, then the last, then the second, then the second to last, and so on until every node is used once.

    Only the links change. Values stay where they are, no nodes are created, and nothing is returned: the list still starts at head.

    The list [1, 2, 3, 4] becomes [1, 4, 2, 3]. The list [1, 2, 3, 4, 5] becomes [1, 5, 2, 4, 3], with the middle node, 3, left over at the end. With two nodes, [4, 8], nothing moves.

    Approach: split, reverse the back half, interleave

    A list can't be walked backwards, so reaching the last node, then the second to last, is the hard part. Copying the nodes into a slice would make it easy, but that costs O(n) extra space, and the lesson asks for O(1). The alternative is to rearrange the list itself in three passes:

    1. Find the middle and cut the list there. 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 2 -> 3 and 4 -> 5.
    2. Reverse the second half. 4 -> 5 becomes 5 -> 4. Now the back of the list can be walked from its front.
    3. Merge the halves, taking one node from each in turn. 1 -> 2 -> 3 and 5 -> 4 give 1 -> 5 -> 2 -> 4 -> 3.

    Each pass visits each node a constant number of times, so the time is O(n), and only a few pointers are kept, so the extra space is O(1).

    To find the middle, use two pointers: slow moves one node at a time and fast moves two. When fast can't move two more nodes, slow is on the last node of the first half. For four nodes, the loop stops with slow on 2 and fast on 3. For five nodes, it stops with slow on 3 and fast on 5. With an odd count, the middle node stays in the first half, and it is the node that ends the final list.

    Step by step

    Find the middle

    1. Create slow and fast, both set to head.
    2. Loop while fast has two nodes after it: fast.Next != nil && fast.Next.Next != nil. Go has no while, so a for with only a condition does the job. The first test comes first, so fast.Next.Next is never read through a nil pointer.
    3. Move slow one node and fast two nodes in each round.

    Cut and reverse the second half

    1. Remember the second half's start in node := slow.Next.
    2. Cut the list with slow.Next = nil. The first half must end at slow. Without the cut, the merge produces a list that never ends: for [1, 2, 3, 4], following the links from the head gives 1 4 2 3 3 3 3 3 ..., with the last node pointing at itself.
    3. Declare prev as var prev *ListNode, the head of the reversed part, empty for now. Short declaration with := can't be used here, because there is no value to take the type from.
    4. Loop while node != nil. Each round turns one node around: save node.Next in nextNode (otherwise the rest of the half is lost), point node.Next at prev, move prev to node, and move node to nextNode.

    Merge the halves

    1. Create first at head and second at prev: the fronts of the first half and of the reversed second half. For 1 -> 2 -> 3 -> 4 -> 5 they are 1 -> 2 -> 3 and 5 -> 4.
    2. Loop while second != nil. The second half is never longer than the first, so when it runs out, every node is placed, and a leftover first-half node is already at the end.
    3. Save where each half continues: nextFirst := first.Next and nextSecond := second.Next.
    4. Link second after first with first.Next = second, then the rest of the first half after second with second.Next = nextFirst.
    5. Advance both pointers to the saved nodes, first = nextFirst and second = nextSecond.

    The solution in Go

    func reorderList(head *ListNode) {
    slow := head
    fast := head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    node := slow.Next
    slow.Next = nil
    var prev *ListNode
    for node != nil {
        nextNode := node.Next
        node.Next = prev
        prev = node
        node = nextNode
    }
    first := head
    second := prev
    for second != nil {
        nextFirst := first.Next
        nextSecond := second.Next
        first.Next = second
        second.Next = nextFirst
        first = nextFirst
        second = nextSecond
    }
}

    Go details worth knowing:

    • Pointers are the list. head is a *ListNode, and node.Next = prev changes the node that node points to, which is why the function can reorder the caller's list without returning anything.
    • Short-circuit &&. In the loop condition, fast.Next.Next is read only when fast.Next isn't nil. Swapping the two tests would panic on lists of odd length.
    • The zero value of a pointer is nil. var prev *ListNode is exactly the empty reversed list, and the first node turned around gets nil as its Next.
    • Parallel updates in the merge. Both next nodes are saved before either link changes, because first.Next and second.Next are both overwritten right after.
    • The list must have a node. The constraints promise at least one. A nil head would panic at fast.Next with a nil pointer dereference.

    Complexity

    Time: O(n). Finding the middle takes about n / 2 rounds, reversing the second half takes about n / 2 rounds, and the merge takes about n / 2 rounds. Each round does a constant amount of work.

    Space: O(1). The function uses a fixed number of pointers (slow, fast, node, prev, first, second and the saved next nodes), and no recursion.

    Edge cases and common mistakes

    • One node. [7] stays [7]. The middle loop doesn't run, node is nil, nothing is reversed, and second is nil so the merge doesn't run.
    • Two nodes. [4, 8] stays [4, 8]. slow stays on the first node, the second node is split off and linked straight back after it.
    • Three nodes. [1, 2, 3] becomes [1, 3, 2].
    • Even length. [1, 2, 3, 4, 5, 6] becomes [1, 6, 2, 5, 3, 4]: the halves have the same length, and the merge ends with the last node of the first half.
    • Forgetting the cut. The first half still points into the second half, and the merged list ends in a cycle, as shown above.
    • Reversing before saving node.Next. After node.Next = prev, the rest of the half can no longer be reached.

    Testing

    • [1, 2, 3, 4] gives [1, 4, 2, 3].
    • [1, 2, 3, 4, 5] gives [1, 5, 2, 4, 3].
    • [4, 8] gives [4, 8].
    • [7] gives [7].
    • [1, 2, 3] gives [1, 3, 2].
    • [1, 2, 3, 4, 5, 6] gives [1, 6, 2, 5, 3, 4].
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free