Advanced Topic

Medium Linked List Algorithms

Master advanced linked list techniques including cycle detection with Floyd's algorithm, finding cycle start nodes, locating middle elements, merging sorted lists, and removing nodes from the end in a single pass.

1. Properties

▸

Two-Pointer Technique: Many advanced LL algorithms use slow/fast pointers moving at different speeds to achieve O(n) time with O(1) space.

▸

Dummy Head Node: Simplifies edge cases when modifying the head pointer (adding/removing head node).

▸

Cycle Detection: Floyd's algorithm detects cycles using tortoise (slow) and hare (fast) pointers without extra space.

▸

Single Pass Solutions: All algorithms here solve their problem in one pass through the list.

2. Key Operations

Detect CycleFloyd's Cycle-FindingTwo pointers at different speeds detect if/where fast laps slow

Find Cycle StartTwo-Phase Floyd'sPhase 1 finds meeting, Phase 2 finds cycle origin

Find MiddleSlow & Fast PointersFast moves 2x speed, slow is at middle when fast reaches end

Merge Sorted ListsCompare & LinkPick smaller head from each list until one is exhausted

Remove N-th from EndGap TechniqueMove first pointer n steps ahead, then move both until first reaches end

3. Complexity Analysis

AlgorithmTimeSpacePasses

Detect CycleO(n)O(1)1

Find Cycle StartO(n)O(1)2

Find MiddleO(n)O(1)1

Merge SortedO(n+m)O(1)1

Remove N-th from EndO(n)O(1)1

4. Visual: Two-Pointer Technique

Slow & Fast Pointers (Find Middle):

  HEAD
    │
    ▼
  ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
  │ 10│ ──►│ 20│ ──►│ 30│ ──►│ 40│ ──►│ 50│ ──► null
  └───┴───┘   └───┴───┘   └───┴───┘   └───┴───┘   └───┴───┘
    S           S            S            F            F
   (1)         (2)          (3)          (4)          (5)

  Fast moves 2 steps, Slow moves 1 step
  When Fast reaches end → Slow is at middle


Cycle Detection:

  HEAD
    │
    ▼
  ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
  │ 10│ ──►│ 20│ ──►│ 30│ ──►········
  └───┴───┘   └───┴───┘   └───┴───┘     │
         ▲                           │
         │                           │
         └───────────────────────────┘
           (cycle back to index 0)

  Slow: 0 → 1 → 2 → 3 → 0 → 1 → ...
  Fast: 0 → 2 → 0 → 2 → 0 → 2 → ...
                          ↑
                      They meet here!

Slow & Fast Pointers (Find Middle): HEAD │ ▼ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ │ 10│ ──►│ 20│ ──►│ 30│ ──►│ 40│ ──►│ 50│ ──► null └───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘ S S S F F (1) (2) (3) (4) (5) Fast moves 2 steps, Slow moves 1 step When Fast reaches end → Slow is at middle Cycle Detection: HEAD │ ▼ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ │ 10│ ──►│ 20│ ──►│ 30│ ──►········ └───┴───┘ └───┴───┘ └───┴───┘ │ ▲ │ │ │ └───────────────────────────┘ (cycle back to index 0) Slow: 0 → 1 → 2 → 3 → 0 → 1 → ... Fast: 0 → 2 → 0 → 2 → 0 → 2 → ... ↑ They meet here!