Part 5 of 14

Linked Lists

Pointer rewiring, cycle detection, k-way merge, LRU cache. Bridges to Part 13's design problems.

Chapters
6
Hours
2
Difficulty
Intermediate
  1. 5.0beginner

    Linked list fundamentals: sentinels, pointer rewiring, doubly-linked design

    Sentinel and dummy nodes erase the boundary branching that special-cases head and tail. The pointer-rewiring discipline and the doubly-linked design every later chapter in Part 5 assumes.

    20 min
  2. 5.1intermediate

    Reversal patterns

    Reverse a singly-linked list in place with prev, curr, next. The snapshot-then-clobber rule, plus the iterative and recursive forms that show up as a primitive in every later linked-list chapter.

    15 min
  3. 5.2intermediate

    Reverse in groups of k

    Three mechanical phases stacked on single-list reversal solve LeetCode 25 in O(1) extra memory, with the seam between groups handled cleanly.

    15 min
  4. 5.3intermediate

    Cycle detection (Floyd's tortoise and hare)

    Two pointers, one stepping twice as fast as the other, locate a cycle's entry node in O(n) time and O(1) space. The modular-arithmetic three-line proof of why the second-phase reset works.

    20 min
  5. 5.4intermediate

    Merging linked lists

    Merge sorted linked lists in place. The dummy-head trick that erases the first-node special case, two-list and k-list versions, and the heap-based and divide-and-conquer extensions to LC 23.

    15 min
  6. 5.5intermediate

    LRU cache: hash map plus doubly linked list

    Build the data structure behind LeetCode 146 from a doubly-linked list and a hash map. O(1) get and put with explicit list management, no shortcut through Python's OrderedDict.

    20 min