View on NeetCode
View on LeetCode

Problem

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

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:

  • The number of nodes in the list is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 1000

Solution

Approach: Find Middle + Reverse + Merge

The key insight is to break the problem into three steps:

  1. Find the middle of the list using slow/fast pointers
  2. Reverse the second half of the list
  3. Merge the two halves by alternating nodes

Implementation

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return

        # Step 1: Find the middle of the list
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Step 2: Reverse the second half
        second = slow.next
        slow.next = None  # Split the list
        prev = None
        while second:
            next_node = second.next
            second.next = prev
            prev = second
            second = next_node
        second = prev  # New head of reversed second half

        # Step 3: Merge the two halves
        first = head
        while second:
            # Save next pointers
            next_first = first.next
            next_second = second.next

            # Reorder
            first.next = second
            second.next = next_first

            # Move pointers
            first = next_first
            second = next_second

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes. We make three passes: finding middle (n/2), reversing (n/2), and merging (n/2).
  • Space Complexity: O(1), we only use a constant amount of extra space.

Key Insights

  1. Three-Step Decomposition: Breaking the problem into find-middle, reverse, and merge makes it manageable. Each step is a standard linked list operation.

  2. Fast/Slow Pointer for Middle: Using two pointers (one moving twice as fast) finds the middle in one pass. When fast reaches the end, slow is at the middle.

  3. Split Before Reverse: We must split the list (slow.next = None) before reversing the second half to avoid cycles.

  4. Merge Pattern: We alternate nodes from the two halves. The first half is always equal or one node longer than the second half after splitting.

  5. In-Place Modification: We modify the existing list structure without allocating new nodes, achieving O(1) space complexity.

  6. Even vs Odd Length: For odd-length lists, the middle node stays with the first half. For even-length lists, we split exactly in half. Both cases are handled by the same logic.