Start learning free

LESSON 378 OF 540 · LINKED LISTS

Reorder List in Scala: Middle, Reverse and Merge in O(n) Time, O(1) Space

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

    SCALA · LINKED LISTS

    Reorder List in Scala, explained

    Problem overview

    The method reorderList gets head, the first node of a singly linked list with at least one node. The lesson provides the ListNode class, whose nodes have a next link. The list L0 -> L1 -> ... -> Ln must become L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: the first node, then the last, then the second, then the second to last, and so on. Only links change. The values stay where they are, no new nodes are created, and the method returns Unit: the list still starts at head.

    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. A list of two nodes, such as 4->8, doesn't change.

    Approach: three passes

    The new order alternates between the front of the list and its back. A singly linked list can't be walked backwards, so reaching the last node from the front costs a full pass each time. Copying the nodes into an array would solve that, but it uses O(n) extra space. The goal here is O(n) time and O(1) space, and three simple passes get there:

    1. Find the middle and cut the list there. A slow pointer moves one node at a time and a fast pointer moves two. When the fast pointer reaches the end, the slow one is in the middle. Cutting after it splits 1->2->3->4->5 into 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 two 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 total stays linear, and the only extra memory is a handful of pointers.

    Step by step

    Find the middle

    1. Declare slow and fast with var, both starting at head, since both will move.
    2. Loop while fast has two more nodes after it: fast.next != null && fast.next.next != null. The loop stops while fast still has nodes in front of it, so slow ends on the last node of the first half: the 2nd of 4 nodes, the 3rd of 5.
    3. Move slow one node forward.
    4. Move fast two nodes forward. The loop condition has already checked that both exist.
    5. Remember the second half: store slow.next in node, a var, because it will move.
    6. Cut the list: set slow.next to null. Without the cut, the first half would still point into the second, and the reordered list would loop.

    Reverse the second half

    1. Declare prev as a var of type ListNode, set to null. It is the head of the part already reversed, empty at the start.
    2. Loop while node != null. Each round turns one node around.
    3. Save node.next in nextNode, because the next line overwrites the link.
    4. Point node.next back at prev.
    5. Move prev to node, which is now the head of the reversed part.
    6. Move node to nextNode.

    Merge

    1. Declare first at head and second at prev, the head of the reversed half.
    2. Loop while second != null. The second half is never longer than the first, so when it runs out, every node is in place, and a leftover node of the first half is already at the end.
    3. Save the next node of each half in nextFirst and nextSecond, since both links are about to change.
    4. Link second after first: first.next = second.
    5. Link the rest of the first half after second: second.next = nextFirst.
    6. Advance both pointers to nextFirst and nextSecond.

    The solution in Scala

    class Solution {
    def reorderList(head: ListNode): Unit = {
        var slow = head
        var fast = head
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next
            fast = fast.next.next
        }
        var node = slow.next
        slow.next = null
        var prev: ListNode = null
        while (node != null) {
            val nextNode = node.next
            node.next = prev
            prev = node
            node = nextNode
        }
        var first = head
        var second = prev
        while (second != null) {
            val nextFirst = first.next
            val nextSecond = second.next
            first.next = second
            second.next = nextFirst
            first = nextFirst
            second = nextSecond
        }
    }
}

    The Scala details worth noticing:

    • var for pointers that move, val for saved values. slow, fast, node, prev, first and second are reassigned, so they are var. nextNode, nextFirst and nextSecond are set once per round, so they are val.
    • var prev: ListNode = null needs the type. Without it, Scala infers the type Null for the variable, and assigning a node to it later fails with Found: ListNode, Required: Null.
    • null is the end of the list. A node's next is null at the tail. In the loop condition, && stops at the first false, so fast.next.next is read only when fast.next is not null.
    • Assigning to a field. slow.next = null changes the node itself. The nodes are objects shared by every variable pointing to them, which is why re-linking them changes the list that head starts.
    • The method returns Unit. Its last expression is the while loop, which has no value, so nothing needs to be returned, and head keeps its place as the first node.

    Complexity

    Time: O(n). Finding the middle visits about half of the nodes. Reversing the second half visits each of its nodes once, and the merge walks it once more. Every pass is linear.

    Space: O(1). The method uses a fixed number of pointers and creates no nodes. It re-links the ones that exist.

    Edge cases and common mistakes

    • One node. 7 stays 7. The loop condition is false at once, slow.next is null, the reversal does nothing, and the merge loop never runs.
    • Two nodes. 4->8 stays 4->8: the second half is just 8, and merging puts it right back after 4.
    • Odd and even lengths. For 1->2->3->4, the slow pointer stops on 2, and for 1->2->3->4->5 it stops on 3. In the odd case, the first half is one node longer, and that node ends the result. 1->2->3 becomes 1->3->2.
    • Forgetting to cut. Without slow.next = null, the first half still reaches into the second, and the merged list contains a cycle.
    • Losing the rest while reversing. Changing node.next before saving it in nextNode throws away the unreversed part of the list.
    • Losing the rest while merging. The same goes for first.next and second.next: both are saved before any link changes.

    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 Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free