Start learning free

LESSON 373 OF 535 · LINKED LISTS

Reorder List in C++: Find the Middle, Reverse, Merge in 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 a vector 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

    C++ · LINKED LISTS

    Reorder List in C++, explained

    Problem overview

    The method reorderList receives head, the first node of a singly linked list with at least one node. The nodes in order are L0, L1, L2, ..., Ln. The method must re-link them so the list reads L0, Ln, L1, Ln-1, L2, Ln-2, and so on: first node, last node, second node, second to last, until every node is used once. It returns nothing, it changes only the next links (no values change and no nodes are created), and the list still starts at head.

    The lesson provides the node type, ListNode, with an int val and a ListNode *next. For 1->2->3->4 the list becomes 1->4->2->3. For 1->2->3->4->5 it becomes 1->5->2->4->3, where the middle node 3 is left over and ends the list. A two-node list such as 4->8 stays as it is.

    Approach: split, reverse the back half, interleave

    The result takes nodes alternately from the front and from the back. A singly linked list can only be walked forward, so reaching the back nodes one by one is awkward. One fix is to copy the nodes into a vector and index from both ends, but that needs O(n) extra space. The goal here is O(n) time and O(1) extra space, so the nodes must be re-linked in place. That takes three passes:

    1. Find the middle and cut. Two pointers walk the list: slow moves one node at a time and fast moves two. When fast can't go further, slow is on the last node of the first half. 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 nodes can be walked from the last node backwards.
    3. Interleave. Take one node from each half in turn: 1->5->2->4->3.

    With an odd count, the first half is one node longer, and its extra node is the middle one. It needs no moving, because after the interleaving it is already last.

    Step by step

    1. Declare slow and fast as ListNode*, both set to head.
    2. Loop while fast->next && fast->next->next: while fast has two more nodes ahead. A null pointer counts as false, so the two pointers are the whole condition. The first test also guards the second, because && stops at the first false operand.
    3. Advance slow by one node and fast by two. The loop condition guaranteed that both of those nodes exist.
    4. Save the second half. It starts at slow->next; store that in node.
    5. Cut the list with slow->next = nullptr. Without the cut, the first half would still lead into the second, and the result would loop.
    6. Start the reversal with prev set to nullptr: the head of the already reversed part, empty at first.
    7. Loop while node is not null. Each round turns one node around.
    8. Save node->next in nextNode before changing it, or the rest of the half is lost.
    9. Point node->next at prev, then move prev to node and node to nextNode.
    10. After the loop, prev is the head of the reversed half. Declare first as head and second as prev.
    11. Loop while second is not null. The second half is never longer than the first, so when it runs out every node has been placed.
    12. Save first->next and second->next in nextFirst and nextSecond, because the next two lines overwrite both links.
    13. Link first->next to second, then second->next to nextFirst. The back node now sits between two front nodes.
    14. Move on: first to nextFirst and second to nextSecond. Nothing is returned, because head is still the first node.

    The solution in C++

    class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* node = slow->next;
        slow->next = nullptr;
        ListNode* prev = nullptr;
        while (node) {
            ListNode* nextNode = node->next;
            node->next = prev;
            prev = node;
            node = nextNode;
        }
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            ListNode* nextFirst = first->next;
            ListNode* nextSecond = second->next;
            first->next = second;
            second->next = nextFirst;
            first = nextFirst;
            second = nextSecond;
        }
    }
};

    Here is the middle search on two lists. On 1->2->3->4->5 the loop stops with slow at 3 and fast at 5. On 1->2->3->4 it stops with slow at 2 and fast at 3. So slow always ends on the last node of the first half, which is the larger half when the count is odd.

    For 1->2->3->4->5 the state after each phase is:

    after the cut:      1->2->3   and   4->5
after the reversal: 1->2->3   and   5->4
after the merge:    1->5->2->4->3

    C++ details worth a closer look:

    • Pointers in conditions. A null pointer converts to false and any other pointer to true, so while (node) means "while node is not nullptr".
    • Short-circuit &&. In fast->next && fast->next->next, the right side is evaluated only when fast->next is non-null, so it never dereferences a null pointer.
    • -> versus .. The variables hold addresses of nodes, so fields are reached with ->. Assigning slow = slow->next moves the pointer, and assigning slow->next = nullptr changes the node it points at.
    • No allocation. The method never calls new. Every node that comes out is one that went in, which is the meaning of re-linking in place.
    • The pointer head is not reassigned. The first node stays first, so the caller's pointer is still correct without passing it by reference.

    Complexity

    Time: O(n). Finding the middle visits about n/2 nodes with slow. The reversal visits the second half once, and the merge visits it once more. Each pass is linear and there are three of them.

    Space: O(1). The method uses a fixed number of pointers (slow, fast, node, prev, nextNode, first, second, nextFirst, nextSecond) and no recursion, whatever the length of the list.

    Edge cases and common mistakes

    • One node. For 7, the loop does not run, slow->next is already nullptr, the second half is empty, and nothing changes.
    • Two nodes. 4->8 stays 4->8. The second half is 8, and linking it after 4 changes nothing.
    • Three nodes. 1->2->3 becomes 1->3->2.
    • Even and odd lengths. The loop condition leaves slow on the 2nd node of 4 and the 3rd node of 5, so the first half is never shorter than the second. That is what lets the merge loop run on second alone.
    • Forgetting the cut. If slow->next keeps pointing at the second half, the merged list ends in a cycle and printing it never stops.
    • Losing the rest of a list. In both the reversal and the merge, the next node must be saved before a link is overwritten.
    • Returning a new head. The function returns nothing. The head is the same node before and after.

    Testing

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