Problem Description

You are given the head of a singly linked list. The task is to reorder the list by alternating nodes from the beginning and end of the list.

Given a linked list with nodes L0 → L1 → L2 → ... → Ln-1 → Ln, you need to rearrange it to follow this pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...

In other words:

• Take the first node from the start (L0)
• Then take the last node (Ln)
• Then take the second node from the start (L1)
• Then take the second-to-last node (Ln-1)
• Continue this pattern until all nodes are processed

The reordering must be done in-place by changing the node connections. You cannot modify the values stored in the nodes - only the links between nodes can be changed.

For example:

• Input: 1 → 2 → 3 → 4 becomes 1 → 4 → 2 → 3
• Input: 1 → 2 → 3 → 4 → 5 becomes 1 → 5 → 2 → 4 → 3

The solution approach involves three main steps:

1. Find the middle of the list using fast and slow pointers - the slow pointer moves one step while the fast pointer moves two steps
2. Reverse the second half of the list starting from the node after the middle
3. Merge the two halves by alternating nodes from the first half and the reversed second half

Intuition

Looking at the reordering pattern, we need to alternate between nodes from the start and nodes from the end of the list. The challenge is that in a singly linked list, we can only traverse forward - we can't easily access nodes from the end.

The key insight is to observe what's happening: we're essentially weaving together two sequences - the first half of the list going forward (L0, L1, L2...) and the second half going backward (Ln, Ln-1, Ln-2...).

If we could somehow have two separate lists - one containing the first half and another containing the second half in reverse order - then we could simply merge them by alternating nodes. This transforms our problem into three simpler subproblems:

1. Split the list in half: We need to find where to split. Using the fast and slow pointer technique is perfect here - when the fast pointer reaches the end (moving 2 steps at a time), the slow pointer (moving 1 step at a time) will be at the middle.

2. Reverse the second half: Once we have the second half separated, we need to reverse it so that we can access what were originally the last nodes first. This way, Ln-1 → Ln becomes Ln → Ln-1.

3. Merge alternately: With the first half as L0 → L1 → L2... and the reversed second half as Ln → Ln-1 → Ln-2..., we can now easily alternate between them to create the desired pattern.

This approach is elegant because it breaks down a complex reordering problem into three well-known, simple operations on linked lists. Each step has O(n) time complexity and uses O(1) extra space, making the entire solution efficient.

Solution Approach

Let's walk through the implementation step by step, following the three-phase approach we identified:

Phase 1: Find the Middle Using Fast and Slow Pointers

fast = slow = head
while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

We initialize both fast and slow pointers at the head. The fast pointer moves two steps at a time while the slow pointer moves one step. When the fast pointer reaches the end, the slow pointer will be at the middle. The condition fast.next and fast.next.next ensures we don't get null pointer errors.

For a list of length n:

• If n is even, slow stops at position n/2 - 1
• If n is odd, slow stops at position n/2 (the middle element)

Phase 2: Split and Reverse the Second Half

cur = slow.next
slow.next = None

First, we save the start of the second half in cur and disconnect it from the first half by setting slow.next = None.

pre = None
while cur:
    t = cur.next
    cur.next = pre
    pre, cur = cur, t

Now we reverse the second half using the standard reversal technique:

• Save the next node in temporary variable t
• Point current node backward to pre
• Move pre and cur forward

After this loop, pre points to the head of the reversed second half.

Phase 3: Merge the Two Halves Alternately

cur = head
while pre:
    t = pre.next
    pre.next = cur.next
    cur.next = pre
    cur, pre = pre.next, t

Starting from the head of the first half (cur = head), we weave the nodes:

• Save the next node from the second half in t
• Insert the node from the second half (pre) after the current node from the first half
• Connect pre to what was originally after cur
• Move forward: cur moves to what is now two positions ahead, pre moves to the saved next node

The merging continues until all nodes from the second half are processed (while pre). Since the second half has at most the same number of nodes as the first half (or one less), this ensures all nodes are properly reordered.

Time and Space Complexity:

• Time: O(n) - we traverse the list a constant number of times
• Space: O(1) - only using a few pointer variables, no extra data structures

Example Walkthrough

Let's walk through the solution with the list: 1 → 2 → 3 → 4 → 5

Initial State:

1 → 2 → 3 → 4 → 5

Phase 1: Find the Middle

We use two pointers - slow (moves 1 step) and fast (moves 2 steps):

• Start: slow = 1, fast = 1
• Step 1: slow = 2, fast = 3
• Step 2: slow = 3, fast = 5
• Stop (fast.next is null)

The slow pointer is now at node 3, which is our middle point.

Phase 2: Split and Reverse Second Half

First, we split at the middle:

First half:  1 → 2 → 3 → null
Second half: 4 → 5 → null

Now reverse the second half (4 → 5):

• Initially: pre = null, cur = 4
• Step 1: Make 4 point to null, move forward
  • Result: 4 → null, pre = 4, cur = 5
• Step 2: Make 5 point to 4, move forward
  • Result: 5 → 4 → null, pre = 5, cur = null

Reversed second half: 5 → 4 → null

Phase 3: Merge Alternately

Now we have:

• First half: 1 → 2 → 3
• Second half (reversed): 5 → 4

Merging process:

• Start: cur = 1, pre = 5
• Step 1: Insert 5 after 1
  • Result: 1 → 5 → 2 → 3, move cur to 2, pre to 4
• Step 2: Insert 4 after 2
  • Result: 1 → 5 → 2 → 4 → 3, move cur to 3, pre to null
• Stop (pre is null)

Final Result: 1 → 5 → 2 → 4 → 3

Each phase operates in linear time with constant space, making this approach both time and space efficient.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. This is because:

• The first while loop finds the middle of the list using two pointers (fast and slow), which takes O(n/2) = O(n) time
• The second while loop reverses the second half of the list, which takes O(n/2) = O(n) time
• The third while loop merges the two halves by alternating nodes, which takes O(n/2) = O(n) time
• Overall: O(n) + O(n) + O(n) = O(n)

The space complexity is O(1). The algorithm only uses a constant amount of extra space for pointer variables (fast, slow, cur, pre, t), regardless of the input size. No additional data structures like arrays or new linked list nodes are created.

Common Pitfalls

1. Incorrect Middle Point Detection for Even-Length Lists

One of the most common mistakes is misunderstanding where the slow pointer ends up in even-length lists. The condition while fast.next and fast.next.next: causes the slow pointer to stop at different relative positions depending on the list length.

The Problem: For a list like 1 → 2 → 3 → 4, developers often assume the split will be symmetric (2 nodes each), but the algorithm actually splits it as:

• First half: 1 → 2
• Second half: 3 → 4

If you use while fast and fast.next: instead, the slow pointer would advance one more position, giving:

• First half: 1 → 2 → 3
• Second half: 4

This asymmetric split would break the merging logic since the first half would have more than one extra node.

Solution: Stick with while fast.next and fast.next.next: to ensure the first half has at most one more node than the second half. This guarantees the merge loop works correctly.

2. Forgetting to Disconnect the Two Halves

The Problem: Omitting the line slow.next = None creates a cycle in the list. Without disconnecting, the first half still points to the second half, which gets reversed. This creates a circular reference that leads to infinite loops during merging.

For example, without disconnection in list 1 → 2 → 3 → 4:

• After reversal, you'd have: 1 → 2 → 3 and 3 also points back via the reversed chain
• This creates a cycle that breaks the merge logic

Solution: Always remember to set slow.next = None immediately after identifying the start of the second half. This cleanly separates the two halves before reversal.

3. Incorrect Merge Pointer Movement

The Problem: A subtle but critical error occurs in the merge step with this line:

cur, pre = pre.next, t

Developers might mistakenly write:

cur = cur.next  # Wrong!
pre = t

The issue is that after inserting pre between cur and cur.next, the original cur.next is now at pre.next. Moving cur to its original next would skip the newly inserted node, causing incorrect ordering.

Solution: Use cur = pre.next (or the combined assignment shown) to correctly advance to what was originally the next node in the first half, which is now two positions ahead after the insertion.

4. Edge Case: Single Node or Empty List

The Problem: The algorithm assumes at least two nodes exist. For a single node or empty list, the fast/slow pointer logic might fail or be unnecessary.

Solution: Add an early return check:

if not head or not head.next:
    return

This handles both empty lists and single-node lists efficiently without running through unnecessary steps.