Start learning free

LESSON 379 OF 541 · LINKED LISTS

Reorder List in Swift: Find the Middle, Reverse, Merge

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

    SWIFT · LINKED LISTS

    Reorder List in Swift, explained

    Problem overview

    The method reorderList(_ head: ListNode?) receives the head of a singly linked list L0 -> L1 -> ... -> Ln and rearranges it, in place, into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: first node, last node, second node, second to last, and so on. Only the links may change. The values stay where they are in their nodes, no node is created, and nothing is returned: the list still starts at head. The lesson provides ListNode, a class with a val and an optional next.

    For [1, 2, 3, 4] the result is [1, 4, 2, 3]. For [1, 2, 3, 4, 5] it is [1, 5, 2, 4, 3], with the middle node 3 left over at the end. For [4, 8] nothing changes, because the last node already follows the first.

    Approach: three passes with O(1) extra space

    Copying the nodes into an array would make this easy, but it uses O(n) extra space. The in-place idea splits the job into three passes, each a classic list technique:

    1. Find the middle and cut the list there. A slow pointer moves one node at a time and a fast pointer two. When the fast one reaches the end, the slow one is in the middle. Cutting after it gives two lists: 1 -> 2 -> 3 and 4 -> 5.
    2. Reverse the second half. 4 -> 5 becomes 5 -> 4. Now walking the second half from its front visits the nodes in the order the answer needs: last, second to last, and so on.
    3. Merge the halves by alternating: one node from the first half, then one from the second.

    Each pass touches each node a constant number of times, so the total time is O(n).

    Step by step

    1. Create the two pointers. head is a ListNode?, but the list has at least one node, so head! unwraps it. Declare slow and fast with var and set both to head!; they are plain ListNode values.
    2. Loop while fast has two more nodes ahead: fast.next != nil && fast.next!.next != nil. The first test makes the ! in the second safe.
    3. Move slow one node to slow.next!.
    4. Move fast two nodes to fast.next!.next!. The loop condition guaranteed both exist.
    5. Remember the second half: var node = slow.next. With an odd number of nodes, the middle stays at the end of the first half.
    6. Cut the list with slow.next = nil. Without the cut, the first half would still lead into the second, and the merged list would loop.
    7. Start the reversal. var prev: ListNode? = nil is the head of the part already reversed, empty at first. The type is written out because nil alone doesn't say what kind of optional it is.
    8. Loop while node != nil, turning one node around per round.
    9. Save the next node first: let nextNode = node!.next. The next line overwrites node!.next, and without the copy the rest of the half would be lost.
    10. Point node!.next back at prev, which reverses that link.
    11. Move prev to node: it is now the head of the reversed part.
    12. Move node to nextNode, the next node to turn.
    13. Prepare the merge. After the loop prev heads the reversed second half. Set first to head and second to prev, both with var.
    14. 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 node of the first half already sits at the end.
    15. Save where each half continues: nextFirst and nextSecond, both let.
    16. Link second after first: first!.next = second.
    17. Link the rest of the first half after second: second!.next = nextFirst.
    18. Advance both pointers to nextFirst and nextSecond.

    A trace on five nodes

    For [1, 2, 3, 4, 5], the first loop ends with slow on 3 and fast on 5. For [1, 2, 3, 4], it ends with slow on 2 and fast on 3. So the first half is the larger one when the count is odd.

    After the cut, the five-node list is split into [1, 2, 3] and [4, 5]. After the reversal loop, the halves are [1, 2, 3] and [5, 4]. The merge then produces [1, 5, 2, 4, 3].

    The solution in Swift

    class Solution {
    func reorderList(_ head: ListNode?) {
        var slow = head!
        var fast = head!
        while fast.next != nil && fast.next!.next != nil {
            slow = slow.next!
            fast = fast.next!.next!
        }
        var node = slow.next
        slow.next = nil
        var prev: ListNode? = nil
        while node != nil {
            let nextNode = node!.next
            node!.next = prev
            prev = node
            node = nextNode
        }
        var first = head
        var second = prev
        while second != nil {
            let nextFirst = first!.next
            let nextSecond = second!.next
            first!.next = second
            second!.next = nextFirst
            first = nextFirst
            second = nextSecond
        }
    }
}

    The Swift details worth a closer look:

    • A constant parameter, a mutable list. head is a let parameter, yet the function changes the list. ListNode is a class, a reference type, so the parameter holds a reference, and changing next on a node changes the node itself. Only reassigning head would be forbidden, and the function never needs to.
    • Why head is still the head. The first node never moves: the first node is always the first in the result. Nothing has to be returned.
    • Optionals and !. slow and fast are non-optional because they start from head! and only move to nodes known to exist. node, prev, first and second stay optional, since they must be able to become nil. Each ! is guarded by the loop condition, and force-unwrapping a nil would crash the program.
    • Comparing with nil. node != nil works even though ListNode has no equality of its own: Swift compares any optional with nil directly.

    Complexity

    Time: O(n). Finding the middle visits about half the nodes, the reversal visits the second half once, and the merge visits each node once.

    Space: O(1). The function uses a handful of pointers and creates no nodes. The nodes are class instances, so relinking them allocates nothing.

    Edge cases and common mistakes

    • One node. [7] stays [7]: fast.next is nil, the second half is empty, and the merge loop never runs.
    • Two nodes. [4, 8] stays [4, 8].
    • Three nodes. [1, 2, 3] becomes [1, 3, 2].
    • Odd versus even length. For six nodes the result is [1, 6, 2, 5, 3, 4]. With an odd length, the middle node ends the list.
    • Forgetting the cut. Without slow.next = nil, the first half still points into the second, and the merged list gets a cycle.
    • Losing the rest while reversing. Overwriting next before saving it throws away the remainder of the list.
    • A loop condition without the second test. Checking only fast.next != nil would let fast.next!.next! unwrap a nil on lists with an even length, and crash.

    Testing

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