Linked List Techniques — The Complete Guide

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

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

// A linked list: 1 → 2 → 3 → null
// node1.val = 1, node1.next = node2
// node2.val = 2, node2.next = node3
// node3.val = 3, node3.next = null  ← end of list

function buildOrModifyList(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);  // dummy node before the real head
  dummy.next = head;
  let curr = dummy;

  // ... do your work using curr ...

  return dummy.next;  // the real head (might have changed)
}
// Why: Without dummy, you'd need special-case logic for
// "what if I need to remove the head?" or "what if the list is empty?"

function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;

  while (curr) {
    const next = curr.next;  // save
    curr.next = prev;        // reverse
    prev = curr;             // advance prev
    curr = next;             // advance curr
  }

  return prev; // new head
}
// Variations:
// - Reverse between positions m and n (save connection points)
// - Reverse in groups of k (reverse k nodes, recurse/loop for rest)

// Find middle node (for even-length, returns first middle)
function findMiddle(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

  while (fast?.next?.next) {  // stops slow at first middle
    slow = slow!.next;
    fast = fast.next.next;
  }

  return slow;
}

// Detect cycle (Floyd's algorithm)
function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;  // they met → cycle exists
  }

  return false; // fast reached end → no cycle
}

// Find cycle entry point
function detectCycleStart(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;

  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (!fast?.next) return null; // no cycle

  slow = head; // reset slow to head
  while (slow !== fast) {
    slow = slow!.next;
    fast = fast!.next;  // both move at speed 1 now
  }

  return slow; // meeting point = cycle start
}

function mergeTwoLists(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }

  tail.next = l1 ?? l2; // attach remaining nodes

  return dummy.next;
}
// Time: O(n + m) | Space: O(1) — we reuse existing nodes

function removeNthFromEnd(
  head: ListNode | null,
  n: number
): ListNode | null {
  const dummy = new ListNode(0, head);
  let first: ListNode | null = dummy;
  let second: ListNode | null = dummy;

  // Advance first by n+1 steps (so second lands BEFORE the target)
  for (let i = 0; i <= n; i++) {
    first = first!.next;
  }

  // Move both until first reaches the end
  while (first) {
    first = first.next;
    second = second!.next;
  }

  // second is now right before the node to remove
  second!.next = second!.next!.next;

  return dummy.next;
}
// Why n+1? Because we need second to stop ONE node BEFORE the target
// so we can rewire second.next to skip the target.

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

  // Step 1: Find middle (fast & slow)
  let slow = head, fast = head;
  while (fast.next?.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }

  // Step 2: Reverse second half (3-pointer reversal)
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow.next;
  slow.next = null; // cut the list in half
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Step 3: Merge two halves alternately (interleave)
  let first: ListNode | null = head;
  let second: ListNode | null = prev;
  while (second) {
    const tmp1 = first!.next;
    const tmp2 = second.next;
    first!.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}
// 1→2→3→4→5 → split: [1→2→3] + [5→4] → merge: 1→5→2→4→3

function sortList(head: ListNode | null): ListNode | null {
  if (!head?.next) return head; // base case: 0 or 1 node

  // Find middle and split
  let slow = head, fast = head.next;
  while (fast?.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  const mid = slow.next;
  slow.next = null; // cut

  // Recursively sort both halves
  const left = sortList(head);
  const right = sortList(mid);

  // Merge sorted halves (Template 3)
  return mergeTwoLists(left, right);
}
// Time: O(n log n) | Space: O(log n) for recursion stack

Input: 1 → 2 → 3 → 4 → null

Initial state:
  prev = null
  curr = 1 → 2 → 3 → 4 → null

Step 1: next = 2, reverse: 1 → null, advance
  prev = 1 → null
  curr = 2 → 3 → 4 → null

Step 2: next = 3, reverse: 2 → 1, advance
  prev = 2 → 1 → null
  curr = 3 → 4 → null

Step 3: next = 4, reverse: 3 → 2, advance
  prev = 3 → 2 → 1 → null
  curr = 4 → null

Step 4: next = null, reverse: 4 → 3, advance
  prev = 4 → 3 → 2 → 1 → null
  curr = null  ← loop ends

Return prev: 4 → 3 → 2 → 1 → null ✓

Key: At each step, we only change ONE pointer (curr.next = prev).
The "next" variable saves our place so we don't lose the rest of the list.

Input: 1 → 2 → 3 → 4 → 5 → 3 (cycle back to node 3)

Step 1: slow=1, fast=1
Step 2: slow=2, fast=3
Step 3: slow=3, fast=5
Step 4: slow=4, fast=4  ← THEY MET! Cycle detected.

Why does this work?
- If there's no cycle, fast reaches null → we return false.
- If there IS a cycle, fast enters the cycle first.
- Once both are in the cycle, fast gains 1 step per iteration.
- The gap closes by 1 each step → they MUST meet.

Finding the cycle START (phase 2):
- After meeting, reset slow to head.
- Move both at speed 1.
  slow=1, fast=4
  slow=2, fast=5
  slow=3, fast=3  ← THEY MET at node 3 = cycle start!

Why? Mathematical proof: the distance from head to cycle start
equals the distance from meeting point to cycle start (mod cycle length).

List A: 1 → 2 → 3 ↘
                        7 → 8 → null
List B:     4 → 5 → 6 ↗

Length A path: 1→2→3→7→8 = 5 nodes
Length B path: 4→5→6→7→8 = 5 nodes

Trick: When pointer A reaches end, redirect to head of B.
       When pointer B reaches end, redirect to head of A.

pA: 1 → 2 → 3 → 7 → 8 → [switch to B] → 4 → 5 → 6 → 7 ✓
pB: 4 → 5 → 6 → 7 → 8 → [switch to A] → 1 → 2 → 3 → 7 ✓

Both travel exactly (lenA + lenB) steps before meeting at node 7!

Why? After switching, both pointers have "compensated" for the
length difference. They're now the same distance from the intersection.
If no intersection, both reach null at the same time.

What does the problem ask?
├── Reverse the list (or part of it)?
│   ├── Entire list → 3-pointer iterative reversal
│   ├── Between positions m and n → Bounded reversal with boundary tracking
│   └── In groups of k → Count k ahead, reverse group, chain groups
├── Find something positional?
│   ├── Middle node → Fast & slow pointers
│   ├── Nth from end → Two-pointer gap technique
│   └── Intersection point → Two-pass redirect trick
├── Detect or handle a cycle?
│   ├── Does cycle exist? → Fast & slow, check if they meet
│   └── Where does cycle start? → Floyd's: meet → reset → walk at same speed
├── Merge or sort?
│   ├── Merge 2 sorted lists → Dummy head + compare walk
│   ├── Merge k sorted lists → Min-heap or divide-and-conquer
│   └── Sort a linked list → Merge sort (find middle + split + merge)
└── Rearrange nodes?
    ├── Palindrome check → Find middle + reverse half + compare
    ├── Reorder list → Find middle + reverse half + interleave
    └── Partition around value → Two dummy lists + reconnect