Start learning free

LESSON 378 OF 540 · LINKED LISTS

Reorder List in Kotlin: O(n) Time and O(1) Space with Three Passes

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

    KOTLIN · LINKED LISTS

    Reorder List in Kotlin, explained

    Problem overview

    The function reorderList receives 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 field. 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. The function returns nothing. It only changes links, the list still starts at head, and no nodes are created.

    The list 1->2->3->4 becomes 1->4->2->3. The list 1->2->3->4->5 becomes 1->5->2->4->3, where the middle node, 3, ends the list. A list of two nodes, such as 4->8, stays as it is.

    Approach: split, reverse, merge

    A singly linked list can only be walked forward, so reaching the last node and then the second to last is awkward. Copying the nodes into an array would allow indexing from both ends, but it costs O(n) extra space. The lesson asks for O(1) extra space, so the work is done on the links in three passes:

    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 is near the end, the slow one is in the middle. For 1->2->3->4->5 the halves are 1->2->3 and 4->5.
    2. Reverse the second half. 4->5 becomes 5->4, so it can be walked from the node that must come first.
    3. Merge the halves alternately. Take one node from the first half, then one from the reversed second half: 1->5->2->4->3.

    Each pass visits every node at most once, so the total time is O(n). The pointers are a fixed handful of variables, so the extra space is O(1).

    Step by step

    Pass 1: find the middle.

    1. Declare slow and fast as vars of type ListNode, both starting at the head. The parameter is ListNode?, so head!! asserts it isn't null. After that Kotlin knows head is not null, so fast can take it directly.
    2. Loop while fast has two more nodes after it: fast.next != null && fast.next!!.next != null. The !! is needed because next is a var property, so Kotlin doesn't smart-cast it. The first half of the condition has just checked it.
    3. Move slow one node and fast two nodes in the loop. The condition guarantees both nodes exist.

    The loop ends with slow on the last node of the first half: the second of 4 nodes, the third of 5. For lists of length 1 to 5 that is nodes at positions 1, 1, 2, 2 and 3.

    Cut. Store slow.next in node, which is where the second half begins, then set slow.next = null. Without the cut, the first half would still lead into the second half, and the merged list would loop back on itself.

    Pass 2: reverse the second half.

    1. Start prev as null, with the type ListNode?. It is the head of the part already reversed, which is empty at first.
    2. Loop while node != null. Save node.next in nextNode, because the next line overwrites it.
    3. Point node.next at prev, move prev to node, and move node to nextNode.

    Pass 3: merge.

    1. Set first to head and second to prev, both typed ListNode? because they become null at the end.
    2. Loop while second != null. The second half is never longer than the first, so when it runs out every node is placed. A leftover node in the first half is already at the end.
    3. Save what comes next in each half: nextFirst and nextSecond. The !! in first!!.next is safe, since first has a node whenever second does.
    4. Re-link: first.next = second, then second.next = nextFirst.
    5. Advance first to nextFirst and second to nextSecond.

    The solution in Kotlin

    class Solution {
    fun reorderList(head: ListNode?) {
        var slow: ListNode = head!!
        var fast: ListNode = 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: ListNode? = head
        var second: ListNode? = prev
        while (second != null) {
            val nextFirst = first!!.next
            val nextSecond = second.next
            first.next = second
            second.next = nextFirst
            first = nextFirst
            second = nextSecond
        }
    }
}

    The Kotlin details worth a closer look:

    • Nullable types. ListNode? may hold null, and ListNode may not. head!! turns the nullable value into a non-null one, and throws a NullPointerException if it was null. The lesson guarantees at least one node.
    • Smart casts. After head!!, Kotlin knows head is not null, so var fast: ListNode = head compiles. Inside while (second != null), second is smart-cast to non-null because it is a local variable. After first!!.next, first is smart-cast too, so first.next = second compiles. A property such as fast.next can't be smart-cast, since it might change between the check and the use, which is why fast.next!!.next appears.
    • The type of node. var node = slow.next infers ListNode?, which is what the reversal loop needs, because nextNode is null after the last node.
    • The order of assignments in the reversal and the merge matters: always save the node you are about to overwrite a link of.

    Complexity

    Time: O(n). Finding the middle takes about n / 2 iterations, the reversal handles about n / 2 nodes, and the merge handles about n / 2 pairs. Each iteration does a constant amount of work.

    Space: O(1). Only a fixed number of pointers are used, and the recursion-free loops allocate nothing. Nodes are re-linked, not copied, so even a list of 50,000 nodes needs no extra memory proportional to its size.

    Edge cases and common mistakes

    • One node. 7 stays 7: the fast pointer can't move, the second half is empty, and the merge loop never runs.
    • Two nodes. 4->8 stays as it is, because the last node already follows the first.
    • 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.
    • Repeated values. 5->5->5->5 comes out as four 5s. The algorithm moves nodes, not values, so equal values cause no trouble.
    • Forgetting the cut. If slow.next stays linked to the second half, the first half's last node still points into it, and the merged list can contain a cycle.
    • Losing the rest of a list. Changing node.next before saving it in nextNode drops the remaining nodes. The same goes for first.next and second.next in the merge.

    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.

    For 1->2->3->4, after the first pass slow is on 2, the halves are 1->2 and 3->4, and after the reversal the second half is 4->3. For 1->2->3->4->5, slow ends on 3 and fast on 5.

    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free