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.

Additional information

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

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]

Brute Force (Array Deque)

Intuition

The problem asks us to alternate between taking nodes from the start and the end of the list. Since a Singly Linked List only allows traversal in one direction, accessing the "end" repeatedly is slow (O(n)).

A simple way to solve this is to store all nodes in a standard Python list (or Deque). This allows O(1) access to both the front and back. We can then use two pointers to reconstruct the list.

Algorithm

1. Traverse the linked list and store all nodes in a list nodes.
2. Initialize l = 0 and r = len(nodes) - 1.
3. While l < r:

• Set nodes[l].next = nodes[r].
• Increment l.
• if l >= r: break.
• Set nodes[r].next = nodes[l].
• Decrement r.

4. Set nodes[l].next = None to avoid cycles.

def reorder_list(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head: return
    
    # Step 1: Store nodes in a list
    nodes = []
    curr = head
    while curr:
        nodes.append(curr)
        curr = curr.next
        
    # Step 2: Reorder using two pointers
    l, r = 0, len(nodes) - 1
    while l < r:
        nodes[l].next = nodes[r]
        l += 1
        
        if l >= r: break
        
        nodes[r].next = nodes[l]
        r -= 1
        
    nodes[l].next = None
    return head

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the list once to fill the array, and once more to reorder pointers.

• Space complexity: O(n)

• Reason: We store all n nodes in a list.

Reverse Second Half (Optimal)

Intuition

To solve this in O(1) space, we need to avoid storing all nodes.
We can break the problem into three steps:

1. Find the Middle: Split the list into two halves.
2. Reverse the Second Half: This allows us to iterate the second half backwards (which effectively becomes "forward" iteration).
3. Merge: Merge the first half and the reversed second half node by node.

Algorithm

1. Find Middle: Use the slow/fast pointer technique. slow will end up at the middle.
2. Reverse Second Half:

• Let second = slow.next.
• Set slow.next = None (cut off the first half).
• Reverse the list starting at second.

3. Merge:

• Initialize first = head and second = prev (head of reversed list).
• While second is not None:
• Save tmp1 = first.next and tmp2 = second.next.
• first.next = second.
• second.next = tmp1.
• Move pointers: first = tmp1, second = tmp2.

def reorder_list(head: Optional[ListNode]) -> Optional[ListNode]:
    # Find middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    second = slow.next
    prev = slow.next = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp

    # Merge two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2
    return head

Time & Space Complexity

• Time complexity: O(n)

• Reason: Finding the middle takes O(n/2), reversing takes O(n/2), and merging takes O(n/2).

• Space complexity: O(1)

• Reason: We only use a few pointers (slow, fast, prev, etc.) to manipulate the list in-place.