Start learning free

LESSON 377 OF 539 · LINKED LISTS

Reorder List in C#: Middle, Reverse and 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 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

    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 lesson provides the ListNode class: the code uses its val and next fields. The list L0 -> L1 -> ... -> Ln must become L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: the first node, the last, the second, the second to last, and so on.

    Only the links change. The values stay as they are and no new nodes are created. The method returns nothing: the list still starts at head, and the caller prints it from there.

    • [1, 2, 3, 4] becomes [1, 4, 2, 3].
    • [1, 2, 3, 4, 5] becomes [1, 5, 2, 4, 3]. The middle node, 3, is left over and ends the list.
    • [4, 8] stays [4, 8], because the last node already follows the first.

    Approach: three passes

    The difficulty is reaching the last node. In a singly linked list there is no way to step backwards, so "take a node from the end" isn't directly possible. Copying the nodes into an array would solve that but costs O(n) extra space. The in-place solution uses three simple passes instead:

    1. Find the middle and cut the list there. 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. Merge the halves, alternating. Take one node from the first half, then one from the reversed second half, and repeat: 1->5->2->4->3.

    The middle is found with two pointers. slow moves one node per step and fast moves two, so when fast runs out of list, slow is halfway. The loop stops while fast still has nodes after it, which leaves slow on the last node of the first half: the 2nd node of 4, and the 3rd node of 5. With an odd count, the middle node therefore stays in the first half, and it is exactly the node that ends the reordered list.

    On [1, 2, 3, 4, 5], the code stops with slow on 3 and fast on 5. After the cut, the first half is 1->2->3 and the second is 4->5. After the reversal, the second half is 5->4. The merge then runs twice: after the first round the list reads 1->5->2->3, and after the second it reads 1->5->2->4->3.

    Step by step

    Find the middle and cut

    1. Declare slow and fast, two ListNode variables, both set to head.
    2. Loop while fast.next != null && fast.next.next != null. That means fast has two more nodes ahead, so it can safely jump two. The first test also protects the second one from a null fast.next.
    3. Move slow one node, to slow.next.
    4. Move fast two nodes, to fast.next.next.
    5. Remember the second half: ListNode node = slow.next.
    6. Cut with slow.next = null. Without the cut, the first half would still flow into the second, and after the merge the list would loop back on itself.

    Reverse the second half

    1. Declare prev as null. It is the head of the part already reversed, which is empty at first.
    2. Loop while node != null. Each round turns one node around.
    3. Save node.next in nextNode. The next line overwrites that link, and without the copy the rest of the half would be lost.
    4. Point node.next at prev, which is the reversal itself.
    5. Move prev to node, the new head of the reversed part.
    6. Move node to nextNode.

    Merge the halves

    1. Declare first as head and second as prev, the heads of the two halves.
    2. Loop while second != null. The second half is never longer than the first. When it runs out, every node is placed, and a leftover node of the first half is already at the end.
    3. Save the next nodes of both halves in nextFirst and nextSecond, because the next two lines change both links.
    4. Link first.next = second, so a node from the back follows a node from the front.
    5. Link second.next = nextFirst, so the rest of the first half follows.
    6. Advance first to nextFirst and second to nextSecond.

    The solution in C#

    class Solution {
    public void ReorderList(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode node = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (node != null) {
            ListNode nextNode = node.next;
            node.next = prev;
            prev = node;
            node = nextNode;
        }
        ListNode first = head;
        ListNode second = prev;
        while (second != null) {
            ListNode nextFirst = first.next;
            ListNode nextSecond = second.next;
            first.next = second;
            second.next = nextFirst;
            first = nextFirst;
            second = nextSecond;
        }
    }
}

    The C# details worth knowing:

    • Nodes are references. ListNode is a class, so a variable such as slow holds a reference to a node, not a copy. Assigning slow = slow.next moves the reference, while assigning slow.next = null changes the node itself, and everything holding that node sees the change.
    • void is enough. The method changes the nodes in place, and the caller's head still points to the first node, which doesn't move. Reassigning the parameter head inside the method would not affect the caller's variable.
    • Short-circuit &&. In fast.next != null && fast.next.next != null, the right side is evaluated only when the left side is true. Swapping the two tests would throw a NullReferenceException on lists with an odd number of nodes, where fast ends on the last node.
    • null for "no node". The reversal starts with prev = null, so the old first node of the second half ends the reversed list.

    Complexity

    Time: O(n). Finding the middle takes about n/2 steps. The reversal and the merge each visit every node of the second half once. Each pass is linear, and there are three of them.

    Space: O(1). The method only re-links existing nodes and uses a fixed number of reference variables. The loops are iterative, so there is no recursion depth to worry about on lists of up to 50,000 nodes.

    Edge cases and common mistakes

    • One node. The loop doesn't run, slow.next is already null, the second half is empty, and the merge loop doesn't run. The list is unchanged.
    • Two nodes. The second half is the last node, reversing one node changes nothing, and the merge makes first.next point to the node it already pointed to. [4, 8] stays [4, 8].
    • Odd and even lengths. With 3 nodes the result is 1->3->2, and with 6 nodes it is 1->6->2->5->3->4.
    • Forgetting the cut. The first half keeps pointing into the second, and the final list forms a cycle.
    • Losing the rest of a half. In the reversal and in the merge, the next node must be saved before a link is overwritten.
    • Cutting too early. If the first half were shorter than the second, the merge would run out of first-half nodes while second-half nodes remain, and first.next would throw a NullReferenceException.
    • Creating new nodes or changing values. The task forbids both. Only next links change.

    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