143. Reorder List - Detailed Explanation

Problem Statement

Description:
You are given the head of a singly linked list:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to:

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

You must do this in-place without altering the node values (i.e., you can only change the pointers).

Examples:

• Example 1:

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

  Output:
  [1, 4, 2, 3]

  Explanation:
  The list is reordered by alternating nodes from the start and end: first node (1), last node (4), second node (2), then third node (3).

• Example 2:

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

  Output:
  [1, 5, 2, 4, 3]

  Explanation:
  The list is reordered to: first node (1), last node (5), second node (2), second-to-last node (4), and finally the middle node (3).

Constraints:

• The number of nodes in the list is in the range [1, 5 * 10⁴].
• The node values can be any valid integers.

Hints Before Diving into the Solution

• Hint 1:
  One way to think about the problem is to split it into parts. First, identify the middle of the list. Then, reverse the second half and merge the two halves alternately.

• Hint 2:
  While a brute-force solution might use extra space (like an array or list to store nodes), consider how you can do it in-place by manipulating the pointers directly. Think about the classic "fast and slow pointers" technique to find the middle.

Approaches

Approach 1: Using Extra Space

Idea:

1. Traverse and Store Nodes:
   Store all the nodes in an array or list.
2. Reorder Using Two Pointers:
   Use two pointers (one starting at the beginning and one at the end) to select nodes alternately.
3. Relink Nodes:
   Iterate through the list of nodes and relink them in the new order.

Drawbacks:

• Space Complexity:
  This approach uses extra space proportional to the number of nodes, which violates the in-place requirement for this problem.

Approach 2: Optimal In-Place Solution

Idea:

This approach involves three main steps:

1. Find the Middle:
   Use the fast and slow pointer technique to find the middle of the linked list.

2. Reverse the Second Half:
   Reverse the linked list starting from the middle (or the node right after the middle) to the end.

3. Merge the Two Halves:
   Merge the first half and the reversed second half alternately.

Detailed Steps:

• Step 1 (Find Middle):
  Initialize two pointers: slow and fast. Move slow by one step and fast by two steps until fast reaches the end. Now slow points to the middle.

• Step 2 (Reverse Second Half):
  Starting from slow.next, reverse the second half of the list. Set slow.next to null to break the list into two parts.

• Step 3 (Merge Halves):
  Use two pointers—one for the first half and one for the reversed second half—and alternate linking nodes until you finish merging.

Visual Example:

Consider the list: 1 → 2 → 3 → 4 → 5

1. Find the Middle:

   • Fast and slow pointers yield slow at node 3.

2. Reverse Second Half:

   • The second half 4 → 5 is reversed to 5 → 4.

3. Merge Halves:

   • Merge nodes alternately:
     • Start with node 1, then node 5, then node 2, then node 4, and finally node 3.

Final reordered list: 1 → 5 → 2 → 4 → 3

Code Implementation

Python Code