Linked Lists

Linked lists are the canonical pointer-manipulation structure. The core mental model: every operation redirects arrows (next pointers) between nodes — you never move data, you re-link. Three foundational techniques: (1) dummy/sentinel node eliminates special-casing the head; (2) slow/fast pointers find midpoints and cycles in one pass; (3) in-place reversal threads nodes onto a reversed prefix. Most hard linked list problems compose these three techniques. Understanding Linked Lists A linked list is a sequence of nodes where each node contains data and a pointer to the next node. Unlike arrays, linked lists don't need contiguous memory — each node can be anywhere in the heap. Why linked lists appear in interviews: They test pointer manipulation skills Many problems require in-place modification They're the foundation for more complex structures (trees, graphs) Key techniques: Dummy head node: simplifies edge cases (empty list, single node) Two pointers (fast/slow): detect cycles, find middle, find nth from end Reversal: iterative (3 pointers) or recursive Merge: combine two sorted lists Common mistakes: Forgetting to handle null/empty list Losing reference to the head after modification Not handling single-node lists Infinite loops when cycle exists Linked Lists Linked lists store elements as nodes connected by pointers. Unlike arrays, elements aren't contiguous in memory. When Linked Lists Beat Arrays O(1) insertion/deletion at known position (vs O(n) for arrays) No need to pre-allocate size Efficient for frequent insert/delete operations Essential Operations Reverse a Linked List (most common interview question): Detect Cycle (Floyd's Algorithm): Merge Two Sorted Lists: Key Problems #206 Reverse Linked List, #21 Merge Two Sorted Lists #141 Linked List Cycle, #146 LRU Cache, #19 Remove Nth From End Interview Tip "I always use a dummy head node when the head might change (merge, delete). It simplifies edge cases." Java Implementation: