Reorder List

Medium Problem 56 of 151 Java and Python

Practice on LeetCode

Problem

You are given the head of a linked list L₀ → L₁ → … → Lₙ₋₁ → Lₙ. Reorder it to L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → …

Change the nodes' links, not their values. Do not return anything.

Example 1

Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Example 2

Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]

Constraints

1 ≤ number of nodes ≤ 5 × 10⁴

Explanation

The result alternates between the front half going forwards and the back half going backwards.

So: find the middle, reverse the second half, then merge the two halves by taking one node from each in turn. That combines three linked list basics.

Approach 1 · Naive

Array of nodes

Time O(n)
Space O(n)

Put the nodes in an array so you can reach the end directly, then relink them with two indexes.

Store every node in an array.
With i from the front and j from the back, link nodes[i] → nodes[j] → nodes[i + 1], moving inwards.
Terminate the list at the last node placed.

Java

import java.util.*;

class Solution {
    public void reorderList(ListNode head) {
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            nodes.add(node);
        }
        int i = 0;
        int j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i == j) {
                break;
            }
            nodes.get(j).next = nodes.get(i);
            j--;
        }
        nodes.get(i).next = null;
    }
}

Python

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        nodes = []
        while head:
            nodes.append(head)
            head = head.next
        i, j = 0, len(nodes) - 1
        while i < j:
            nodes[i].next = nodes[j]
            i += 1
            if i == j:
                break
            nodes[j].next = nodes[i]
            j -= 1
        nodes[i].next = None

Approach 2 · Optimal

Split, reverse, weave

Time O(n)
Space O(1)

Cut the list at the middle, reverse the second half, then interleave the two halves.

Find the middle with slow/fast pointers (slow ends at the end of the first half).
Reverse slow.next … and set slow.next = null to split.
Weave: take a node from the first half, then one from the reversed half, until the second half is used up.

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 second = null;
        ListNode curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = second;
            second = curr;
            curr = next;
        }
        ListNode first = head;
        while (second != null) {
            ListNode firstNext = first.next;
            ListNode secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}

Python

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        second, curr = None, slow.next
        slow.next = None
        while curr:
            curr.next, second, curr = second, curr, curr.next
        first = head
        while second:
            first_next, second_next = first.next, second.next
            first.next = second
            second.next = first_next
            first, second = first_next, second_next

Complexity compared

Approach	Time	Space
Naive Array of nodes	O(n)	O(n)
Optimal Split, reverse, weave	O(n)	O(1)

Key takeaways

Hard list problems are usually a combination of: find the middle, reverse, merge.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem