Start learning free

LESSON 374 OF 536 · LINKED LISTS

Reorder List in Python: 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 a list 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

    PYTHON · LINKED LISTS

    Reorder List in Python, explained

    Problem overview

    The method reorderList(head) receives the first node of a singly linked list with at least one node. It must rearrange the list in place so that the nodes read first, last, second, second to last, and so on, until every node has been used once. The list still starts at head, and the method returns nothing. Only the links between nodes may change: values stay where they are and no new nodes are created.

    The lesson provides the node class, shown in a comment in the starter code: a ListNode with a val and a next that is None at the end of the list.

    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: the middle node, 3, is left over and ends the list. With two nodes, 4 -> 8, nothing moves, since the last node already follows the first.

    Approach: split, reverse, interleave

    A singly linked list can only be walked forward, so reaching the last node, then the second to last, directly isn't possible. An easy way around that is to copy the nodes into a Python list and index it from both ends, but that costs O(n) extra space. The goal here is O(n) time with O(1) extra space, and it takes three passes:

    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. 4 -> 5 becomes 5 -> 4. Now the back of the list can be walked from its front.
    3. Take one node from each half in turn: 1 -> 5 -> 2 -> 4 -> 3.

    With an even count the halves have the same length. With an odd count the first half is one node longer and keeps the middle node, which ends up last, exactly where the answer needs it.

    Step by step

    Finding the middle

    1. Start both pointers at head. Create slow and fast.
    2. Loop while fast.next and fast.next.next. The loop continues only if fast has two more nodes after it, so both steps below are safe. None is falsy, so no explicit comparison is needed. Stopping here leaves slow on the last node of the first half: the 2nd of 4 nodes, the 3rd of 5.
    3. Move slow one node and fast two nodes each round.
    4. Remember the second half. It starts right after slow, so store slow.next in node.
    5. Cut the list: set slow.next = None. Without the cut, slow would still point into the second half, and the final list would loop back on itself. For 1 -> 2 -> 3 -> 4 the uncut version ends in 3 pointing to itself, so printing it never finishes: it reads 1, 4, 2, 3, 3, 3, 3, and so on.

    Reversing the second half

    1. Create prev = None. It is the head of the part already reversed, empty at first.
    2. Loop while node is not None. Each round turns one node around.
    3. Save node.next in nextNode. The next line overwrites node.next, and without the saved copy the rest of the half would be lost.
    4. Point node.next at prev, then move prev to node, then move node to nextNode.

    Interleaving the halves

    1. Create first = head and second = prev, the heads of the first half and the reversed second half. For 1 -> 2 -> 3 -> 4 -> 5 these are 1 -> 2 -> 3 and 5 -> 4.
    2. Loop while second is not None. The second half is never longer than the first, so when it runs out every node is placed, and a leftover middle node is already at the end.
    3. Save where each half continues: first.next in nextFirst and second.next in nextSecond.
    4. Link first.next to second, then second.next to nextFirst, so the node from the back sits between two nodes from the front.
    5. Advance: first to nextFirst and second to nextSecond.

    The solution in Python

    class Solution:
    def reorderList(self, head: ListNode) -> None:
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        node = slow.next
        slow.next = None
        prev = None
        while node:
            nextNode = node.next
            node.next = prev
            prev = node
            node = nextNode
        first = head
        second = prev
        while second:
            nextFirst = first.next
            nextSecond = second.next
            first.next = second
            second.next = nextFirst
            first = nextFirst
            second = nextSecond

    Notes on the Python side:

    • The method returns None. It has no return, so Python returns None by itself. The caller keeps using head, which is still the first node.
    • Variables are references. slow, fast, node and the rest are names for the same node objects, not copies, so slow.next = None really cuts the list.
    • Short-circuit and. In fast.next and fast.next.next, the second part is evaluated only if fast.next is truthy. That prevents an AttributeError from reading .next on None.
    • Assignment order matters. In the loops, each line reads values saved by earlier lines. Reordering the lines would lose nodes.

    Complexity

    Each pass visits each node a constant number of times: finding the middle walks about half the list, reversing walks the second half, and interleaving walks the second half again. The total time is O(n). Only a handful of pointers are used, so the extra space is O(1).

    Edge cases and common mistakes

    • One node. The loop condition fails immediately, slow.next is None, the second half is empty, and nothing changes. [7] stays [7].
    • Two nodes. [4, 8] stays [4, 8]. slow stays on the first node, the second half is just 8, and linking it after 4 reproduces the same list.
    • Three nodes. [1, 2, 3] becomes [1, 3, 2].
    • Forgetting the cut. The list ends in a cycle, as described above.
    • Losing the rest of a half by overwriting a next link before saving it.

    Testing

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