Skip to main content

🟨 Reorder List (#143)

🔗 Problem Link​

📋 Problem Statement​

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.

💡 Examples​

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]

🔑 Key Insights & Approach​

Core Observation: Break problem into three steps:

  1. Find middle using slow/fast pointers
  2. Reverse second half
  3. Merge two halves alternately

Why Three Steps?

  • O(n) time, O(1) space
  • Clean separation of concerns
  • Each step is a standard pattern

Approaches:

  1. Three-step approach: O(n) time, O(1) space - optimal
  2. Stack: O(n) time, O(n) space
  3. Array: O(n) time, O(n) space

Pattern: "Linked List Manipulation" combining multiple patterns.

🐍 Solution: Python​

Approach: Find Middle, Reverse, Merge​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        # Step 1: Find middle using slow/fast pointers
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Step 2: Reverse second half
        second = slow.next
        slow.next = None  # Split list
        prev = None

        while second:
            temp = second.next
            second.next = prev
            prev = second
            second = temp

        second = prev  # Head of reversed second half

        # Step 3: Merge two halves
        first = head
        while second:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first = temp1
            second = temp2

🔵 Solution: Golang​

Approach: Three Steps​

Time Complexity: O(n) | Space Complexity: O(1)

type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // Find middle
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Reverse second half
    second := slow.Next
    slow.Next = nil
    var prev *ListNode

    for second != nil {
        temp := second.Next
        second.Next = prev
        prev = second
        second = temp
    }

    second = prev

    // Merge
    first := head
    for second != nil {
        temp1, temp2 := first.Next, second.Next
        first.Next = second
        second.Next = temp1
        first = temp1
        second = temp2
    }
}

📚 References​