Reorder List: Rearranging Nodes in a Linked List

The "Reorder List" problem is a unique challenge in linked list manipulation, involving the reordering of nodes in a specific pattern.

Problem Statement

Given a singly linked list, reorder it such that the list follows the pattern: first node, last node, second node, second last node, and so on.

Example

• Input: Linked List 1 -> 2 -> 3 -> 4
• Output: Reordered List 1 -> 4 -> 2 -> 3

Solution Approach

class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;

  // Step 1: Find the middle of the list
  let slow: ListNode | null = head,
    fast: ListNode | null = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  // Step 2: Reverse the second half of the list
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow;
  let temp: ListNode | null;
  while (curr) {
    temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }

  // Step 3: Merge the two halves
  let first: ListNode | null = head,
    second: ListNode | null = prev;
  while (second && second.next) {
    temp = first!.next;
    first!.next = second;
    first = temp;

    temp = second.next;
    second.next = first;
    second = temp;
  }
}

Breaking Down the Solution

• Find Middle: Use the fast and slow pointer technique to find the middle of the list.
• Reverse Second Half: Reverse the second half of the list starting from the middle.
• Merge Halves: Alternately merge nodes from the first half and the reversed second half.

Conclusion

The Reorder List problem is an excellent exercise in linked list operations, combining techniques like finding the middle of a list, reversing a list, and merging lists. It showcases complex manipulation of data structures and is a useful skill for many algorithmic challenges.