Start learning free

LESSON 381 OF 543 · LINKED LISTS

Reorder List in Rust: Split, Reverse and Merge in O(n)

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 20
    Ctrl + Enter to check

    RUST · LINKED LISTS

    Reorder List in Rust, explained

    Problem overview

    The function reorder_list receives head, a mutable borrow of a singly linked list: &mut Option<Box<ListNode>>. For a list L0 -> L1 -> ... -> Ln, it must rearrange the nodes into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: the first node, then the last, then the second, then the second to last, and so on. Only the links change. The values stay where they are, no new nodes are created, and nothing is returned, since the list still starts at head.

    The lesson provides ListNode, with an i32 field val, a field next: Option<Box<ListNode>> and a constructor ListNode::new(val). The list has at least one node and at most 50,000.

    The list [1, 2, 3, 4] becomes [1, 4, 2, 3], and [1, 2, 3, 4, 5] becomes [1, 5, 2, 4, 3]. With an odd count, the middle node is left over and ends the list.

    Approach: split, reverse the back half, interleave

    A singly linked list can only be walked forward, so there is no direct way to reach the last node, then the one before it. Copying the nodes into a vector would allow it, but costs O(n) extra space. The in-place solution has three passes:

    1. Split the list after its middle: 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 2 -> 3 and 4 -> 5. The first half is the same size as the second or one node longer.
    2. Reverse the second half. 4 -> 5 becomes 5 -> 4. Now walking the second half from its front visits the original list from its end.
    3. Interleave. Take one node from the first half, then one from the second, and so on: 1 -> 5 -> 2 -> 4 -> 3.

    Each pass visits every node once, so the whole thing is O(n) time, and it only moves links, so the extra space is O(1).

    The usual way to find the middle is two pointers, a slow one that moves one node at a time and a fast one that moves two. In Rust, a second pointer can't stay in the list while the list is being changed, because the borrow checker allows one mutable path into it at a time. The solution counts instead. One read-only pointer, fast, jumps two nodes at a time while a counter, half, goes up by one for each jump. That counter ends up where a slow pointer would be. For lists of 1 to 6 nodes, half ends as 1, 1, 2, 2, 3, 3: the size of the first half. A second walk then goes half - 1 steps from the head, with a mutable borrow, to reach the last node of the first half.

    On [1, 2, 3, 4, 5], the stages are:

    first [1, 2, 3] second [4, 5]
reversed [5, 4]
round 1 leftover second [4] first_has_node=true
round 2 leftover second [] first_has_node=true
[1, 5, 2, 4, 3]

    Round 1 moves 5 behind 1, round 2 moves 4 behind 2, and 3 is already at the end.

    Step by step

    1. Count the first half. Create half as 0 and fast as head.as_ref(), a read-only borrow of the first node. as_ref() looks inside the Option without taking the node out of head.
    2. Loop while fast has a node. while let Some(node) = fast runs as long as fast stands on a node.
    3. Jump two nodes. node.next.as_ref() is the next node, and and_then runs a closure on it only when it exists, giving None otherwise. The closure takes that node's own next in the same way. If node is the last one or the one before it, fast becomes None and the loop ends.
    4. Add 1 to half. The loop runs once for every two nodes, rounded up.
    5. Walk to the end of the first half. slow is a mutable borrow of the first node, from head.as_mut().unwrap(). fast is no longer used, so head can be borrowed mutably.
    6. Loop half - 1 times. for _ in 1..half doesn't need the loop variable. slow starts on the first node, so it takes half - 1 steps to reach node number half.
    7. Step forward. slow = slow.next.as_mut().unwrap() moves to the next node.
    8. Cut the list. slow.next.take() moves the second half into current and leaves None behind, so the first half now ends at slow.
    9. Prepare the reversal. prev is an Option<Box<ListNode>> that starts as None: the part already reversed.
    10. Loop over the second half. while let Some(mut node) = current takes the next node out of current on each round.
    11. Keep the rest. current = node.next.take() leaves node alone and holds the nodes after it in current.
    12. Turn the node around. node.next = prev points it at the nodes reversed so far.
    13. Extend the reversed part. prev = Some(node) makes this node its new front.
    14. Prepare the merge. first is head.as_mut(), a mutable borrow of the first node, and second is prev, which owns the reversed half.
    15. Loop over the second half. while let Some(mut node) = second takes its front node. The second half is never longer than the first, so when it runs out, every node is in place.
    16. Take the front node of the first half. first.unwrap() gives first_node. There is always one here whenever second has a node.
    17. Keep the rest of the second half in second with node.next.take().
    18. Hand over the link. node.next = first_node.next.take() makes node point at the rest of the first half.
    19. Link it in. first_node.next = Some(node) puts the back node right after the front one.
    20. Advance first. Two links after first_node: its next node is the one just inserted, and the one after that is the next node of the first half, borrowed with as_mut(). It stays an Option, which is None once the first half is used up.

    The solution in Rust

    struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

impl Solution {
    fn reorder_list(head: &mut Option<Box<ListNode>>) {
        let mut half = 0;
        let mut fast = head.as_ref();
        while let Some(node) = fast {
            fast = node.next.as_ref().and_then(|next| next.next.as_ref());
            half += 1;
        }
        let mut slow = head.as_mut().unwrap();
        for _ in 1..half {
            slow = slow.next.as_mut().unwrap();
        }
        let mut current = slow.next.take();
        let mut prev: Option<Box<ListNode>> = None;
        while let Some(mut node) = current {
            current = node.next.take();
            node.next = prev;
            prev = Some(node);
        }
        let mut first = head.as_mut();
        let mut second = prev;
        while let Some(mut node) = second {
            let first_node = first.unwrap();
            second = node.next.take();
            node.next = first_node.next.take();
            first_node.next = Some(node);
            first = first_node.next.as_mut().unwrap().next.as_mut();
        }
    }
}

    Rust details worth knowing:

    • Shared then mutable borrows. fast borrows head read-only, and its last use is in the first loop. Rust lets the later head.as_mut() go ahead because the earlier borrow is no longer used.
    • take() moves a value out of an Option. It returns the old contents and leaves None in place. That is how the code detaches nodes from a list it only borrows: you can't move a field out of a borrowed struct, but you can swap it with None.
    • The reversal moves ownership. In while let Some(mut node) = current, each node is moved out of current. The body gives current a new value before the next test, so the loop can continue, and each node ends up owned by prev.
    • Reassigning a borrow. slow = slow.next.as_mut().unwrap() replaces a mutable borrow by a borrow of a node further down the same list, which is how the walk moves forward.
    • first.unwrap() moves the borrow. A &mut inside first is moved out by unwrap, so first must be given a new value before the next round. The last line of the loop does that.
    • No return value. The function changes the list through head, so there is no final expression.

    Complexity

    Time: O(n). Counting walks about n / 2 steps, reaching the middle walks about n / 2 more, reversing visits each node of the second half once, and the merge visits each node of the second half once. The total is a few passes over at most n nodes.

    Space: O(1). Only a few variables are used. Nodes are re-linked, never copied. The loops are iterative, so there is no recursion depth to worry about.

    Edge cases and common mistakes

    • One node. [7] stays [7]. Here half is 1, the walk loop 1..1 doesn't run, slow.next.take() gives None, and the merge loop never starts.
    • Two nodes. [4, 8] stays [4, 8]: the second half is just 8, which is moved to the place it already had.
    • Odd and even lengths. [1, 2, 3] becomes [1, 3, 2] and [1, 2, 3, 4, 5, 6] becomes [1, 6, 2, 5, 3, 4]. The first half is the longer one when the count is odd, which is why the middle node ends the list.
    • Not cutting the list. The take() after the walk is what separates the halves. Without a cut, the first half would still be linked to the second, and the merge would have no end for the first half.
    • A wrong split point. If half were one too small on a list with an odd count, the second half would be longer than the first, and first.unwrap() would run out of nodes to unwrap.
    • Allocating new nodes. The task is to re-link existing nodes. Creating nodes works for small lists, but uses O(n) space.
    • Losing the rest of a list. Each take() before an assignment keeps the rest of a list from being dropped. Reassigning node.next first would throw the nodes after it away.

    Testing

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