Linked Lists

A linked list is a pointer-based sequence of nodes where each node holds a value and a reference to the next node (and optionally the previous one for doubly linked lists).

Variants: Singly, doubly, circular, sentinel/dummy-headed.

Operations and complexity:

• Access by index: O(n)
• Insert/delete at head/tail (with pointer): O(1)
• Insert/delete in middle (with node ref): O(1)
• Search: O(n)
• Space: O(n)

Great for frequent insertions/deletions without shifting elements.

• Interview staple: Reverse list, detect cycle, merge/split lists show up often.
• Teaches pointers and invariants: Careful reference management, dummy nodes, two-pointer techniques.
• Under the hood: Hash table buckets, LRU caches, adjacency lists often rely on linked lists.

Use linked lists when you need:

1. Frequent insert/delete at head/tail or given node.
2. Stable iterators while mutating structure.
3. Queue/stack implementations with O(1) operations.
4. Memory-constrained chunking where contiguous blocks (arrays) are undesirable.

Avoid when you need random access or heavy indexing—arrays perform better.

1. Two Pointers (Fast/Slow) Detect cycles (Floyd), find cycle start, middle of list, intersection of two lists.

2. Reverse List Iterative with three pointers (prev, curr, next) or recursive; reverse sublist [m..n] or in k-groups.

3. Dummy/Sentinel Nodes Simplify head/tail edge cases for insert/delete and merging.

4. Merge/Split Merge two sorted lists, split list into halves (for merge sort), partition list by pivot.

5. In-place Rewiring Reorder list, rotate list, remove Nth from end (two pointers offset by N).

• Reverse linked list; reverse in k-group
• Remove Nth node from end; delete middle node
• Palindrome linked list (reverse second half and compare)
• Merge two lists; merge k sorted lists (heap)
• Reorder list; rotate list; partition list
• Detect cycle; find cycle start; intersection of two lists
• Add two numbers (digits as list)

• Losing references: Save next before rewiring; update pointers in the right order.
• Head/tail updates: Remember to return the new head; maintain tail when needed.
• Infinite loops: Ensure next becomes null where appropriate; handle cycles carefully.
• Off-by-one in sublist reversals: Verify boundaries and iteration counts.
• Not using dummy nodes: Leads to duplicated edge-case code and bugs.
• Index-based thinking: Avoid using indices—use pointers and counts.

1. Need O(1) insert/delete with node ref? → Linked list
2. Random access or frequent indexing? → Array
3. Remove Nth from end? → Two pointers with offset
4. Cycle detection? → Fast/slow pointers (Floyd)
5. Merge/sort list? → Merge two lists; merge sort via split + merge
6. Check palindrome? → Find mid, reverse second half, compare