Command Palette

Search for a command to run...

Hectal

Module 8

Linked Lists

Nodes joined by next pointers: walk them safely, add a dummy head, reverse in place, and use fast and slow pointers to find middles and cycles.

Intermediate 4 lessons 9 problems ~50 min of lessons
In-Place Linked List ReversalFast and Slow PointersDummy Head and MergingK-Way Merge

A linked list trades the array's instant indexing for cheap insertion and removal: changing two pointers splices a node in or out. Almost every linked list problem is about moving pointers in the right order without losing the rest of the list.

Four techniques cover nearly every interview question: careful traversal, the dummy head, in-place reversal, and fast and slow pointers. The module ends with merging k sorted lists, which joins lists with a heap or divide and conquer.

Best after: Two Pointers

Part 1

Learn the ideas

  1. 8.1Nodes and ReferencesHow a linked list is stored, how to walk it without falling off the end, and when it beats an array.12 min
  2. 8.2The Dummy HeadA fake node before the real head means the first node is never a special case when building, inserting or deleting.10 min
  3. 8.3Reversing a List In PlaceWalk with three pointers (prev, curr, next) and turn each arrow around. The building block for many harder list problems.12 min
  4. 8.4Fast and Slow PointersOne pointer moves one step, the other two. They reveal the middle of a list and detect cycles in O(1) space (Floyd's algorithm).14 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 8.1Reverse Linked ListEasyIn-Place Linked List Reversal

    The three-pointer reversal you'll reuse in palindrome checks, reordering and group reversal.

  2. 8.2Middle of the Linked ListEasyFast and Slow Pointers

    Fast and slow pointers find the middle in one pass, without counting the length first.

  3. 8.3Linked List CycleEasyFast and Slow Pointers

    Floyd's cycle detection: a hash set uses O(n) memory; two runners at different speeds need O(1).

  4. 8.4Merge Two Sorted ListsEasyDummy Head and Merging

    Build a new list behind a dummy head by always taking the smaller front node.

  5. 8.5Remove Nth Node From EndMediumDummy Head and Merging

    Two pointers with a fixed gap of n find the node before the target in one pass; a dummy head handles removing the first node.

  6. 8.6Add Two NumbersMediumDummy Head and Merging

    Grade-school addition on linked lists: walk both lists, carry the tens digit, and build the result behind a dummy head.

  7. 8.7Palindrome Linked ListEasyIn-Place Linked List Reversal

    Combine two techniques: find the middle with fast and slow, reverse the second half, then compare.

  8. 8.8Reorder ListMediumIn-Place Linked List Reversal

    Three steps you already know, chained: split at the middle, reverse the second half, weave the halves together.

  9. 8.9Merge K Sorted ListsHardK-Way Merge

    Scale "merge two" to k lists: a min-heap of the k fronts, or pairwise merging in rounds, both O(N log k).