Start learning free

LESSON 374 OF 536 · LINKED LISTS

Reorder List in Java: 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

    JAVA · LINKED LISTS

    Reorder List in Java, explained

    Problem overview

    The method reorderList receives the head of a singly linked list and returns nothing. It must rearrange the nodes in place so that the list reads: first node, last node, second node, second to last node, and so on until every node is used once. Only the links may change. Values stay where they are inside their nodes, and no new nodes are created. The lesson provides the ListNode class, with an int val and a ListNode next.

    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. For 4->8 nothing moves, because 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 and then the second to last is awkward. Copying the nodes into an array would solve that, but it costs O(n) extra space. The in-place solution has three passes:

    1. Find the middle and cut the list there. 1->2->3->4->5 becomes the first half 1->2->3 and the second half 4->5.
    2. Reverse the second half. 4->5 becomes 5->4. Now walking the second half from its front visits the original list from the end.
    3. Interleave the halves, taking one node from each in turn: 1->5->2->4->3.

    The middle is found with two pointers: slow moves one node at a time and fast moves two. When fast reaches the end, slow has covered half the distance. The loop keeps going only while fast has two more nodes after it, so slow stops on the last node of the first half. For five nodes it stops on the third node (value 3), with fast on the fifth. For four nodes it stops on the second, with fast on the third. When the list has an odd number of nodes, the first half is one node longer, and that extra middle node is the one left over at the end of the reordered list.

    Step by step

    Find the middle

    1. Declare slow and fast, both starting at head.
    2. Loop while fast.next != null && fast.next.next != null. Both nodes must exist before fast can jump two ahead.
    3. Move slow one node to slow.next.
    4. Move fast two nodes to fast.next.next.

    Cut and reverse the second half

    1. Store slow.next in node. This is the start of the second half.
    2. Set slow.next = null. The first half must end at slow. Without the cut it would still point into the second half.
    3. Start prev at null. It will be the head of the part already reversed, empty at first.
    4. Loop while node != null, turning one node around per round.
    5. Save node.next in nextNode, because the next line overwrites it.
    6. Point node.next at prev. That is the reversal.
    7. Advance prev to node, then node to nextNode.

    Merge the halves

    1. Set first to head and second to prev, the head of the reversed second half.
    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 first-half node is already at the end.
    3. Save first.next and second.next in nextFirst and nextSecond, because both links are about to change.
    4. Set first.next = second, then second.next = nextFirst. A node from the back now sits between two nodes from the front.
    5. Advance first to nextFirst and second to nextSecond.

    The solution in Java

    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;
        }
    }
}

    Java details worth noticing:

    • The method returns void. It works because head is a reference to a node object, and the method changes the next fields of the nodes that the caller still holds. Reassigning the parameter head inside the method would not be visible outside, but this solution never does that. The first node stays the first node.
    • Short-circuit &&. In fast.next != null && fast.next.next != null, the second test runs only when the first is true. Swapping them would throw NullPointerException on a one-node list.
    • Temporary variables protect the links. Each overwrite of a next field is preceded by saving the old value in a local (nextNode, nextFirst, nextSecond). Without it, the rest of a half would be unreachable.
    • No new nodes. Only references move. The solution allocates nothing beyond a handful of local variables.

    Complexity

    Time: O(n). Finding the middle visits about half of the nodes, reversing visits the second half once, and merging visits each node of the second half once. Each pass is linear.

    Space: O(1). The solution uses a fixed number of references and relinks the nodes that already exist, with no recursion and no array copy.

    Edge cases and common mistakes

    • One node. The loop condition is false at once, slow.next is null, the second half is empty, and nothing changes. The list 7 stays 7.
    • Two nodes. 4->8 stays 4->8. The second half 8 is merged right after 4, which is where it already was.
    • Odd length. 1->2->3 becomes 1->3->2. The middle node, 2, stays in the first half and ends the list.
    • Forgetting the cut. If slow.next keeps pointing into the second half, the merged list can loop back on itself, and printing it never ends.
    • Stopping slow one node too late. If the loop ran while fast != null && fast.next != null, slow would stop on the first node of the second half for even lengths, and the halves would be unbalanced.
    • Overwriting a link before saving it. Setting node.next = prev before saving node.next loses the rest of the half.
    • Repeated values. Values may repeat, for instance six nodes that all hold 5. The algorithm moves nodes by position, not by value, so the list stays correct.
    • Changing values instead of links. Swapping the val fields would break the rule that only links may change.

    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.
    • 5->5->5->5->5->5 stays the same.
    • 1->2->3->4->5->6->7->8 becomes 1->8->2->7->3->6->4->5.

    After the first two passes on 1->2->3->4->5, the halves are 1->2->3 and 5->4, ready to interleave.

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