Skip to content

Topic 7 of 20

Linked List

Pointer manipulation: reversal, fast & slow pointers, merging and cache design.

25 problems8 Easy13 Medium4 Hard

The concept

A linked list stores elements in nodes that point to the next node, so insertion and deletion are O(1) once you are at the right spot, but random access is O(n). Linked-list questions are really pointer-manipulation questions. They test whether you can rewire next pointers without losing part of the list, so draw the boxes and arrows before you code.

Three techniques cover most problems. A dummy head node removes special cases when the real head might change. In-place reversal (keep prev, curr and next) is used on its own and inside harder problems such as reversing in groups of k. Fast & slow pointers, where one moves two steps for every one step of the other, find the middle, detect cycles and even locate the start of a cycle (Floyd's algorithm).

The topic ends with design problems such as the LRU cache, where a hash map gives O(1) lookup and a doubly linked list gives O(1) reordering. That pairing is one of the most frequently asked design questions at every large company.

Patterns you will learn

Problems, in order

  1. 1

    The single most important linked-list routine; do it iteratively and recursively.

    In-place ReversalReported at: AmazonMicrosoftApple+5
  2. 2

    Dummy head plus merge, reused in merge sort and k-way merge.

    Merge Lists + Dummy HeadReported at: AmazonMetaMicrosoft+6
  3. 3

    Floyd's cycle detection in its simplest form.

    Fast & Slow PointersReported at: AmazonMicrosoftGoogle+4
  4. 4

    Fast/slow to find the midpoint, a sub-step of many problems.

    Fast & Slow PointersReported at: AmazonGoogleMeta+3
  5. 5

    Basic pointer skipping on sorted data.

    Pointer SkippingReported at: AmazonMetaMicrosoft+2
  6. 6

    Shows why a dummy head removes head-deletion special cases.

    Dummy HeadReported at: AmazonMicrosoftMeta+1
  7. 7

    Combines finding the middle with reversing the second half.

    Fast & Slow + ReversalReported at: AmazonMetaMicrosoft+7
  8. 8

    Switching heads equalises path lengths, an elegant trick.

    Two Pointers (Length Equalising)Reported at: AmazonMicrosoftMeta+5
  9. 9

    A fixed gap between two pointers in one pass.

    Two Pointers (Gap)Reported at: MetaAmazonMicrosoft+5
  10. 10

    Chains three core routines together; a great consolidation problem.

    Middle + Reverse + MergeReported at: AmazonMicrosoftMeta+4
  11. 11

    Digit-by-digit addition with a carry; very frequently asked.

    Carry PropagationReported at: AmazonMetaApple+8
  12. 12

    Deep copy with arbitrary pointers; the interleaving trick gives O(1) space.

    Hash Map / InterleavingReported at: MetaAmazonMicrosoft+3
  13. 13

    The maths behind finding a cycle's start with Floyd's algorithm.

    Fast & Slow PointersReported at: AmazonMicrosoft
  14. 14

    Treating an array as a linked list to find a cycle; a famous insight.

    Fast & Slow PointersReported at: AmazonMicrosoftMeta+3
  15. 15

    Local pointer rewiring in pairs.

    In-place ReversalReported at: MetaAmazonMicrosoft+3
  16. 16

    Reversal of a sub-range with correct reconnection.

    In-place Reversal (Sublist)Reported at: MetaAmazonMicrosoft+3
  17. 17

    Make a ring, then cut it at the right place.

    Ring + CutReported at: MicrosoftBloomberg
  18. 18

    Partitions nodes into two chains in place.

    Pointer PartitioningReported at: MetaAmazonAdobe+1
  19. 19

    Removing whole runs needs a dummy head and a careful look-ahead.

    Dummy HeadReported at: AmazonMetaMicrosoft
  20. 20
    Sort ListMedium

    Merge sort on a linked list in O(n log n).

    Merge Sort on ListsReported at: MetaAmazonMicrosoft+2
  21. 21
    LRU CacheMedium

    One of the most-asked design questions at every FAANG company.

    Hash Map + Doubly Linked ListReported at: AmazonMetaMicrosoft+17
  22. 22

    Heap-based or divide-and-conquer merging; a classic Hard.

    K-way Merge (Heap / Divide & Conquer)Reported at: MetaAmazonMicrosoft+9
  23. 23

    Group-wise reversal: the hardest pure pointer problem.

    In-place Reversal (Groups)Reported at: AmazonMicrosoftMeta+3
  24. 24

    An LRU follow-up with frequency buckets.

    Hash Map + Frequency BucketsReported at: MicrosoftAmazonGoogle+6
  25. 25

    O(1) inc/dec/min/max with a bucket list.

    Hash Map + Doubly Linked BucketsReported at: AmazonLinkedInVMware