Singly and doubly linked lists. Master the fast-slow pointer technique for cycle detection and middle finding.
Time
Access: O(n), Search: O(n), Insert at head: O(1), Delete: O(1) if node known
Space
O(n)
Problems
5 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Reverse Linked List | Easy | Microsoft Amazon Google |
| 2 | Detect Cycle in Linked List | Easy | Amazon Microsoft TCS |
| 3 | Merge Two Sorted Lists | Easy | Amazon Microsoft Apple |
| 4 | Remove Nth Node From End | Medium | Google Meta Amazon |
| 5 | LRU Cache | Hard | Google Amazon Microsoft |
Always use a dummy head node to simplify edge cases
Fast-slow pointers: slow moves 1 step, fast moves 2 steps
To reverse: keep track of prev, curr, next pointers
Linked lists have poor cache locality compared to arrays
