> ## Documentation Index > Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt > Use this file to discover all available pages before exploring further. # Linked List Patterns > Master pointer manipulation for linked list problems Linked List Pattern ## What is Linked List? **Linked List** is a linear data structure where elements (called nodes) are connected via pointers rather than being stored in contiguous memory. Think of it like a scavenger hunt: each clue (node) tells you where to find the next clue, but you cannot jump directly to clue number 7 without following clues 1 through 6. This gives linked lists O(1) insertions and deletions at a known position (just rewire the pointers) but O(n) access to an arbitrary element (you must walk the chain). Unlike arrays where you pay for shifting elements on insert or delete, a linked list only requires updating a constant number of pointers. The trade-off is that you lose random access and pay extra memory per element for storing the pointer itself. **Quick Recognition**: Problems involving pointer manipulation, in-place modifications, or two-pointer techniques on sequences. Keywords: "reverse", "cycle", "merge lists", "middle node", "reorder", "palindrome". ## Pattern Recognition Cheatsheet **Map keywords in the problem statement to the technique. If you see one of these, reach for the matching template before writing any code.** | Problem Keyword | Technique | Template to Reach For | | ----------------------------------------------------------------------------------- | -------------------------------------------------- | -------------------------------------- | | "reverse the linked list", "reverse from position L to R", "reverse in groups of K" | In-place reversal with three pointers | `prev` / `curr` / `next` template | | "detect cycle", "is there a loop", "find where the cycle begins" | Floyd's tortoise and hare | Fast/slow pointers, then phase 2 reset | | "find the middle node", "split the list in half", "find the kth node" | Fast/slow pointers (or N+1 gap) | Fast moves 2x slow | | "merge two sorted lists", "merge K sorted lists" | Zipper merge with dummy node, or min-heap of heads | Dummy node + tail pointer | | "remove the nth node from the end" | Fast/slow with N+1 gap | Dummy node + two pointer gap | | "remove duplicates from sorted list", "delete all occurrences" | Single pointer with prev/curr | Dummy node + skip-while | | "is the list a palindrome" | Find middle, reverse second half, compare | Compose middle + reverse + walk | | "reorder the list", "rearrange odd/even positions" | Find middle + reverse + interleave | Dummy node + zipper | | "deep copy with random pointer" | HashMap (original to copy) or interleave-and-split | Two-pass clone | | "intersection of two lists" | Two-pointer redirect at end | Switch heads when reaching null | | "design LRU / LFU cache" | Doubly linked list + HashMap | Sentinel head/tail nodes | **Rule of thumb**: if the problem involves a singly linked list and asks for O(1) extra space, it is almost always one of: dummy node, fast/slow, or in-place reversal -- often two of them composed together. ## Universal Templates These three templates cover roughly 90% of linked list interview problems. Memorize them cold; you should be able to write each one in under 60 seconds with no thinking. ```python Python theme={null} # TEMPLATE 1: Dummy node + prev/curr (insert, delete, partition, merge) def template_dummy(head): dummy = ListNode(0, head) # Sentinel before head -- never moves prev = dummy # Tracks the node before curr curr = head # The node being inspected while curr: # ... decide whether to keep, modify, or delete curr ... # To DELETE curr: prev.next = curr.next; curr = curr.next # To KEEP curr: prev = curr; curr = curr.next pass return dummy.next # Always correct -- even if original head was removed # TEMPLATE 2: Fast/slow pointers (cycle detection, find middle, Nth from end) def template_fast_slow(head): slow = fast = head while fast and fast.next: # Stop when fast falls off the end slow = slow.next # 1 step fast = fast.next.next # 2 steps # if slow == fast: cycle detected # When loop exits: slow is at the middle (second middle for even length) return slow # TEMPLATE 3: Reverse in place (full or sublist reversal) def template_reverse(head): prev, curr = None, head while curr: nxt = curr.next # 1. Save -- never lose the rest of the list curr.next = prev # 2. Flip the pointer backwards prev = curr # 3. Advance prev forward curr = nxt # 4. Advance curr forward return prev # prev is the new head ``` ```java Java theme={null} // TEMPLATE 1: Dummy node + prev/curr ListNode templateDummy(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy, curr = head; while (curr != null) { // delete: prev.next = curr.next; curr = curr.next; // keep: prev = curr; curr = curr.next; } return dummy.next; } // TEMPLATE 2: Fast/slow pointers ListNode templateFastSlow(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // TEMPLATE 3: Reverse in place ListNode templateReverse(ListNode head) { ListNode prev = null, curr = head; while (curr != null) { ListNode nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev; } ``` ```javascript JavaScript theme={null} // TEMPLATE 1: Dummy node + prev/curr function templateDummy(head) { const dummy = { val: 0, next: head }; let prev = dummy, curr = head; while (curr) { // delete: prev.next = curr.next; curr = curr.next; // keep: prev = curr; curr = curr.next; } return dummy.next; } // TEMPLATE 2: Fast/slow pointers function templateFastSlow(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; } // TEMPLATE 3: Reverse in place function templateReverse(head) { let prev = null, curr = head; while (curr) { const nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev; } ``` ```cpp C++ theme={null} // TEMPLATE 1: Dummy node + prev/curr ListNode* templateDummy(ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; ListNode* curr = head; while (curr != nullptr) { // delete: prev->next = curr->next; curr = curr->next; // keep: prev = curr; curr = curr->next; } return dummy.next; } // TEMPLATE 2: Fast/slow pointers ListNode* templateFastSlow(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } // TEMPLATE 3: Reverse in place ListNode* templateReverse(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr) { ListNode* nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; } return prev; } ``` **Caveats and Traps -- read these BEFORE you start coding.** 1. **Losing the head pointer.** The single most common linked list bug. The moment you write `head = head.next` or rewire `head.next`, the original head is gone. Always use a dummy node for any operation that might touch the head -- it is one extra allocation that eliminates an entire class of bugs. 2. **Off-by-one in fast/slow when finding middle of an even-length list.** For `1 to 2 to 3 to 4`, the standard `while fast and fast.next` loop lands `slow` on node 3 (the second middle). If you need the first middle (node 2) -- common when splitting for merge sort -- use `while fast.next and fast.next.next` instead. Pick a convention and stick with it. 3. **Modifying the list while iterating breaks cycle detection.** If you remove a node mid-traversal and forget to update both `prev` and `curr`, you can accidentally introduce a cycle or skip the next node. Floyd's algorithm assumes the structure is stable during the scan -- if you mutate, do it via the dummy node template, not on top of the cycle scan. 4. **Forgetting to set the new tail's next to null.** After splitting a list (say, in palindrome check or reorder list), the node that becomes the new tail still points to its old successor. If you do not explicitly set `tail.next = null`, you end up with two intertwined lists or even a cycle. 5. **Reusing variables across iterations.** A `next_node` saved in iteration K is invalid in iteration K+1. Always re-read pointers fresh each loop body. ## Pattern Recognition Checklist * Detecting cycles (Floyd's algorithm) * Finding middle element * Reversing all or part of list * Merging sorted lists * Checking palindrome structure * Removing duplicates * Dummy head for edge cases * Fast/slow pointers for cycle/middle * Prev/curr/next for reversal * Two-pointer for nth from end * In-place to save space ## When to Use Cycle detection, finding middle Reverse entire list or portions Merge sorted lists, intersection Simplify edge case handling ## Pattern Variations ### 1. Fast and Slow Pointers (Floyd's) Imagine two runners on a circular track -- one runs at twice the speed of the other. No matter where they start, the fast runner will eventually lap the slow runner and they will meet. This is the core insight behind Floyd's algorithm: if a cycle exists, the two pointers *must* collide; if no cycle exists, the fast pointer reaches the end first. For finding the middle node, the same idea applies: when the fast pointer reaches the end (having moved 2 steps per iteration), the slow pointer (1 step per iteration) is exactly at the midpoint. **Complexity:** O(n) time, O(1) space for both operations. ```python Python theme={null} class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def has_cycle(head): """Detect cycle in linked list using Floyd's tortoise and hare.""" # Both pointers start at the head of the list slow = fast = head while fast and fast.next: slow = slow.next # Tortoise moves 1 step fast = fast.next.next # Hare moves 2 steps if slow == fast: return True # They met -- cycle confirmed # Fast pointer reached the end, so no cycle exists return False def find_middle(head): """Find middle node (second middle if even length). Example: 1 -> 2 -> 3 -> 4 -> 5 returns node 3 1 -> 2 -> 3 -> 4 returns node 3 (second middle) """ slow = fast = head while fast and fast.next: slow = slow.next # 1 step fast = fast.next.next # 2 steps # When fast reaches the end, slow is at the middle return slow ``` ```java Java theme={null} class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class LinkedListPatterns { public boolean hasCycle(ListNode head) { // Detect cycle in linked list ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } public ListNode findMiddle(ListNode head) { // Find middle node (second middle if even length) ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } } ``` ```cpp C++ theme={null} struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; class LinkedListPatterns { public: bool hasCycle(ListNode* head) { // Detect cycle in linked list ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; } ListNode* findMiddle(ListNode* head) { // Find middle node (second middle if even length) ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } }; ``` ### 2. Reverse Linked List Reversing a linked list is like reversing a chain of paper clips: at each step you detach the current clip from what comes after it and attach it to the growing reversed chain behind you. You need exactly three variables to avoid losing track: `prev` (the already-reversed portion), `current` (the node you are processing), and `next_node` (a temporary save so you do not lose the rest of the list when you rewire `current.next`). **Complexity:** O(n) time, O(1) space for in-place reversal. **Edge cases to watch:** empty list (return None), single-node list (already reversed), and partial reversal where `left == right` (no-op). ```python Python theme={null} def reverse_list(head): """Reverse entire linked list in-place. Walkthrough with 1 -> 2 -> 3: Step 1: prev=None, curr=1 => 1.next = None, prev=1, curr=2 Step 2: prev=1, curr=2 => 2.next = 1, prev=2, curr=3 Step 3: prev=2, curr=3 => 3.next = 2, prev=3, curr=None Result: 3 -> 2 -> 1 """ prev = None current = head while current: next_node = current.next # Save the next node before we break the link current.next = prev # Reverse the pointer: point backwards prev = current # Advance prev to current node current = next_node # Move forward in the original list return prev # prev is now the new head def reverse_between(head, left, right): """Reverse nodes from position left to right (1-indexed). Example: 1 -> 2 -> 3 -> 4 -> 5, left=2, right=4 Result: 1 -> 4 -> 3 -> 2 -> 5 The trick: repeatedly take the node after current and insert it right after prev, effectively building the reversed segment. """ dummy = ListNode(0, head) prev = dummy # Step 1: Navigate prev to the node just before position 'left' for _ in range(left - 1): prev = prev.next # Step 2: Reverse the sublist from left to right current = prev.next for _ in range(right - left): next_node = current.next # Node to be moved to the front current.next = next_node.next # Detach next_node from its position next_node.next = prev.next # Insert next_node right after prev prev.next = next_node # Update prev's next to next_node return dummy.next ``` ```java Java theme={null} public class ReverseLinkedList { public ListNode reverseList(ListNode head) { // Reverse entire linked list ListNode prev = null; ListNode current = head; while (current != null) { ListNode nextNode = current.next; current.next = prev; prev = current; current = nextNode; } return prev; } public ListNode reverseBetween(ListNode head, int left, int right) { // Reverse nodes from position left to right ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; // Move to node before left for (int i = 0; i < left - 1; i++) { prev = prev.next; } // Reverse from left to right ListNode current = prev.next; for (int i = 0; i < right - left; i++) { ListNode nextNode = current.next; current.next = nextNode.next; nextNode.next = prev.next; prev.next = nextNode; } return dummy.next; } } ``` ```cpp C++ theme={null} class ReverseLinkedList { public: ListNode* reverseList(ListNode* head) { // Reverse entire linked list ListNode* prev = nullptr; ListNode* current = head; while (current != nullptr) { ListNode* nextNode = current->next; current->next = prev; prev = current; current = nextNode; } return prev; } ListNode* reverseBetween(ListNode* head, int left, int right) { // Reverse nodes from position left to right ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* prev = dummy; // Move to node before left for (int i = 0; i < left - 1; i++) { prev = prev->next; } // Reverse from left to right ListNode* current = prev->next; for (int i = 0; i < right - left; i++) { ListNode* nextNode = current->next; current->next = nextNode->next; nextNode->next = prev->next; prev->next = nextNode; } return dummy->next; } }; ``` ### 3. Merge Two Sorted Lists This is the "zipper" pattern: given two sorted chains, interleave them into one sorted chain by always picking the smaller head. A dummy node at the start eliminates special-case logic for choosing the initial head. **Complexity:** O(n + m) time where n and m are the lengths of the two lists. O(1) extra space because we re-use existing nodes. **Interview tip:** This same merge logic is the foundation for Merge Sort on linked lists and for the "Merge K Sorted Lists" problem (use a min-heap of heads or pairwise merge). ```python Python theme={null} def merge_two_lists(l1, l2): """Merge two sorted linked lists into one sorted list. Example: l1 = 1 -> 3 -> 5, l2 = 2 -> 4 -> 6 Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6 """ dummy = ListNode(0) # Dummy head avoids edge cases for the first node current = dummy while l1 and l2: if l1.val <= l2.val: # Pick the smaller value to maintain sorted order current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next # Attach whichever list still has remaining nodes current.next = l1 or l2 return dummy.next ``` ```java Java theme={null} public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // Merge two sorted linked lists ListNode dummy = new ListNode(0); ListNode current = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } current.next = (l1 != null) ? l1 : l2; return dummy.next; } ``` ```cpp C++ theme={null} ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // Merge two sorted linked lists ListNode* dummy = new ListNode(0); ListNode* current = dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val <= l2->val) { current->next = l1; l1 = l1->next; } else { current->next = l2; l2 = l2->next; } current = current->next; } current->next = (l1 != nullptr) ? l1 : l2; return dummy->next; } ``` ### 4. Remove Nth Node From End The "gap" technique: advance the fast pointer n+1 steps ahead of slow. Then move both at the same speed. When fast hits None, slow is exactly one node before the target -- perfectly positioned to bypass it. The dummy node handles the edge case where the node to remove is the head itself. **Complexity:** O(n) time with a single pass, O(1) space. **Edge case:** If n equals the length of the list, you are removing the head. Without the dummy node this requires a special check. ```python Python theme={null} def remove_nth_from_end(head, n): """Remove the nth node from the end of the list. Example: 1 -> 2 -> 3 -> 4 -> 5, n=2 Gap setup: fast is 3 nodes ahead of slow (n+1 = 3) When fast = None, slow points to node 3 => remove node 4 Result: 1 -> 2 -> 3 -> 5 """ dummy = ListNode(0, head) slow = fast = dummy # Create a gap of n+1 between fast and slow for _ in range(n + 1): fast = fast.next # Advance both pointers until fast reaches the end while fast: slow = slow.next fast = fast.next # slow.next is the node to remove -- skip over it slow.next = slow.next.next return dummy.next ``` ```java Java theme={null} public ListNode removeNthFromEnd(ListNode head, int n) { // Remove nth node from end using two pointers ListNode dummy = new ListNode(0); dummy.next = head; ListNode slow = dummy, fast = dummy; // Move fast n+1 steps ahead for (int i = 0; i <= n; i++) { fast = fast.next; } // Move both until fast reaches end while (fast != null) { slow = slow.next; fast = fast.next; } // Remove nth node slow.next = slow.next.next; return dummy.next; } ``` ```cpp C++ theme={null} ListNode* removeNthFromEnd(ListNode* head, int n) { // Remove nth node from end using two pointers ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* slow = dummy; ListNode* fast = dummy; // Move fast n+1 steps ahead for (int i = 0; i <= n; i++) { fast = fast->next; } // Move both until fast reaches end while (fast != nullptr) { slow = slow->next; fast = fast->next; } // Remove nth node slow->next = slow->next->next; return dummy->next; } ``` ## Worked LeetCode Problems These five problems are the foundation of every linked list interview. If you can solve all five from memory in under 15 minutes total, you are ready for the medium tier. ### LC 206 -- Reverse Linked List (Easy) **Brute force**: push every value into an array, walk it backwards, build a new list. O(n) time, O(n) space, and you have not demonstrated any pointer skill. **Optimized**: in-place reversal using the three-pointer template. O(n) time, O(1) space. ```python theme={null} def reverseList(head): prev, curr = None, head while curr: nxt = curr.next # save the rest of the list curr.next = prev # flip the link prev = curr # advance prev curr = nxt # advance curr return prev ``` **Recursive variant** (worth knowing for follow-ups): ```python theme={null} def reverseList(head): if not head or not head.next: return head new_head = reverseList(head.next) # reverse everything after head head.next.next = head # the next node now points back to us head.next = None # we are the new tail return new_head ``` The recursive version is O(n) space due to the call stack -- mention this trade-off if asked. ### LC 141 -- Linked List Cycle (Easy) **Brute force**: walk the list and put each visited node reference in a HashSet. If you re-encounter a node, there is a cycle. O(n) time, O(n) space. **Optimized**: Floyd's tortoise and hare. Two pointers, fast moves 2x. If they meet, there is a cycle. O(n) time, O(1) space. ```python theme={null} def hasCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False ``` **Why interviewers prefer Floyd's**: the O(1) space constraint is the entire point. The HashSet solution works but signals you have not internalized the canonical technique. ### LC 21 -- Merge Two Sorted Lists (Easy) **Brute force**: collect all values, sort, build a new list. O((n+m) log(n+m)) time, O(n+m) space. Wastes the existing sorted property entirely. **Optimized**: zipper merge with a dummy node. O(n+m) time, O(1) space (reusing existing nodes). ```python theme={null} def mergeTwoLists(l1, l2): dummy = ListNode(0) tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 # attach the leftover tail return dummy.next ``` **Why the dummy node matters**: without it, you need a special branch for "which list provides the first node?" and another for "what if one list is empty?" The dummy collapses both into one uniform loop. ### LC 19 -- Remove Nth Node From End (Medium) **Brute force**: two passes. First pass counts the length L. Second pass walks to position L - n and unlinks. O(n) time, O(1) space, but two traversals. **Optimized**: one-pass with a fast/slow gap of N+1. O(n) time, O(1) space, single pass. ```python theme={null} def removeNthFromEnd(head, n): dummy = ListNode(0, head) slow = fast = dummy for _ in range(n + 1): # create gap of n+1 fast = fast.next while fast: # walk both until fast falls off slow = slow.next fast = fast.next slow.next = slow.next.next # slow is now exactly before the target return dummy.next ``` **Why N+1 and not N**: with a gap of N+1, when fast reaches null, slow lands on the node *before* the target -- exactly where you need to be to unlink it. With a gap of N, slow lands ON the target, and you have lost the predecessor needed for deletion. ### LC 23 -- Merge K Sorted Lists (Hard) **Brute force 1 -- collect and sort**: gather all N nodes into an array, sort, rebuild. O(N log N) time, O(N) space. **Brute force 2 -- sequential pairwise merge**: merge list 1 with list 2, result with list 3, etc. O(k \* N) time -- the early lists are re-traversed k times. **Optimized A -- min-heap**: push the head of each list onto a min-heap. Pop the smallest, append, push that node's `next`. O(N log k) time, O(k) space. ```python theme={null} import heapq def mergeKLists(lists): heap = [] # Python's heapq compares tuples lexicographically; second element is a tiebreaker # because ListNode is not directly comparable for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy = ListNode(0) tail = dummy while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next ``` **Optimized B -- divide and conquer (pairwise merge)**: pair up the K lists, merge each pair using LC 21. Repeat until one list remains. O(N log k) time, O(log k) recursion depth. Both optimized approaches are O(N log k). In practice divide-and-conquer has slightly better cache behavior for static inputs; the heap is easier to code and adapts to streaming inputs. Mention both in interviews. ## Classic Problems | Problem | Pattern | Key Insight | | --------------- | ------------ | ------------------------------- | | Cycle Detection | Fast/Slow | Floyd's algorithm | | Middle of List | Fast/Slow | Fast moves 2x speed | | Reverse List | Iterative | Track prev, curr, next | | Merge K Lists | Divide/Heap | Merge pairs or use min-heap | | Intersection | Length Diff | Align starts then traverse | | Palindrome | Reverse Half | Reverse second half and compare | ## Interview Problems by Company | Problem | Company | Key Concept | | --------------- | ------------- | -------------------- | | Reverse List | All FAANG | Basic reversal | | Merge Two Lists | All FAANG | Two pointers | | Delete Node | Apple, Amazon | No prev access trick | | Middle of List | Amazon | Fast/slow | | Problem | Company | Key Concept | | -------------------- | ------------ | ----------------------------- | | Add Two Numbers | All FAANG | Carry handling | | Remove Nth from End | Meta, Amazon | Gap technique | | Linked List Cycle II | Amazon | Floyd's + cycle start | | Copy with Random | All FAANG | Interleaving or HashMap | | Reorder List | Meta | Find middle + reverse + merge | | Problem | Company | Key Concept | | --------------- | ------------ | ----------------------- | | Merge K Lists | All FAANG | Heap or divide/conquer | | Reverse K Group | Meta, Google | K-reversal | | LRU Cache | All FAANG | Doubly linked + HashMap | ## Interview Tips A dummy (sentinel) node simplifies every edge case where the head might change -- deletions at the head, insertions before the head, or merges where either list could provide the first node. A senior engineer would say: "The dummy node costs one allocation but saves three if-statements." ```python theme={null} def solve(head): dummy = ListNode(0) dummy.next = head # ... operations that may change head ... return dummy.next # Always correct, even if original head was removed ``` Reversal appears as a sub-routine in many medium and hard problems (palindrome check, reorder list, reverse in k-groups). Memorize the three-variable dance: prev, curr, next\_node. ```python theme={null} def reverse(head): prev, curr = None, head while curr: next_node = curr.next # 1. Save next curr.next = prev # 2. Reverse link prev = curr # 3. Advance prev curr = next_node # 4. Advance curr return prev # New head is the last node we visited ``` **Common mistake:** Forgetting to save `curr.next` before overwriting it. Once you set `curr.next = prev`, the original forward link is gone forever. Phase 1 -- **Detect**: Run fast (2x) and slow (1x). If they meet, a cycle exists. Phase 2 -- **Locate start**: Reset one pointer to head. Move both at 1x speed. They will meet at the cycle entrance. This works because of a mathematical property: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (traveling around the cycle). ```python theme={null} def find_cycle_start(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # Phase 1: cycle detected slow = head # Phase 2: reset slow to head while slow != fast: slow = slow.next fast = fast.next return slow # Both meet at cycle start return None # No cycle ``` **Complexity:** O(n) time, O(1) space -- this is why interviewers love it over the HashSet approach. In an interview, always draw the list before coding. Label each node and use arrows for `next` pointers. When you modify a pointer, erase the old arrow and draw the new one. This prevents the most common class of linked list bugs: losing a reference to a node because you overwrote a pointer before saving it. Ask yourself at every step: "Have I saved every reference I will need later?" ## Practice Problems Basic reversal technique Find cycle start point Divide and conquer or heap Doubly linked list + HashMap ## Practice Roadmap * Solve: Reverse List, Merge Two Lists * Focus: Pointer manipulation * Solve: Middle of List, Cycle Detection, Cycle II * Focus: Floyd's algorithm * Solve: Reorder List, Palindrome Linked List * Focus: Combining techniques * Solve: LRU Cache, Merge K Lists, Reverse K Group * Focus: Design + complex operations **Interview Tip**: Draw the linked list on your whiteboard or scratch pad before writing a single line of code. Visualizing pointer changes helps avoid the number-one linked list bug: overwriting a `.next` pointer before saving the reference you still need. Always test your logic against three cases: empty list (head is null), single node, and two nodes. ## Curated LeetCode List A focused grind list grouped by difficulty. Solve all of these and you can confidently field any linked list question in a 45-minute interview. | # | Problem | Difficulty | Pattern | Why It Matters | | --- | ---------------------------------- | --------------------- | ------------------------------- | ------------------------------------------------------------------- | | 206 | Reverse Linked List | Easy | In-place reverse | The single most-asked linked list problem. Iterative AND recursive. | | 141 | Linked List Cycle | Easy | Fast/slow | Floyd's algorithm in its simplest form. | | 21 | Merge Two Sorted Lists | Easy | Dummy + zipper | Foundation for merge sort and merge K lists. | | 876 | Middle of the Linked List | Easy | Fast/slow | Convention: returns the second middle for even length. | | 83 | Remove Duplicates from Sorted List | Easy | Single pass | Tests basic prev/curr manipulation without a dummy. | | 234 | Palindrome Linked List | Easy | Compose middle + reverse + walk | Classic three-technique composition. | | 160 | Intersection of Two Linked Lists | Easy | Two-pointer redirect | Elegant length-equalization trick. | | 142 | Linked List Cycle II | Medium | Floyd's phase 2 | Find the cycle start. The math is the interview lesson. | | 19 | Remove Nth Node From End | Medium | Fast/slow gap | Canonical N+1 gap technique. | | 92 | Reverse Linked List II | Medium | Sublist reverse | Reverse from L to R in one pass. | | 86 | Partition List | Medium | Two dummies | Classic "split into two then stitch" pattern. | | 2 | Add Two Numbers | Medium | Dummy + carry | Tests off-by-one and carry propagation. | | 24 | Swap Nodes in Pairs | Medium | Dummy + lookahead | Recursive solution is cleaner than iterative -- mention both. | | 138 | Copy List with Random Pointer | Medium | HashMap or interleave-and-split | Two valid solutions with different space trade-offs. | | 143 | Reorder List | Medium | Middle + reverse + zipper | Composes three patterns into one. | | 148 | Sort List | Medium | Merge sort on lists | O(n log n) time, O(log n) recursion. | | 23 | Merge K Sorted Lists | Hard | Heap or D\&C | The K-way merge problem. | | 25 | Reverse Nodes in K-Group | Hard | Reverse subroutine + outer loop | Composes reversal inside a counting loop. | | 146 | LRU Cache | Medium (treated Hard) | Doubly linked + HashMap | The most-asked design question at FAANG. | | 460 | LFU Cache | Hard | Two HashMaps + DLL of DLLs | The harder cousin of LRU. | **Suggested order**: 206 to 141 to 21 to 876 to 234 to 160 to 142 to 19 to 92 to 86 to 2 to 24 to 138 to 143 to 148 to 23 to 25 to 146. ## Interview Q\&A -- Senior-Level Walkthroughs **What interviewers are really testing:** Whether you genuinely understand pointer manipulation or just memorized the iterative template. Asking for both forces you to demonstrate two different mental models, and the follow-up about space complexity reveals whether you understand the call stack. **Strong Answer Framework:** 1. State the technique: "Iterative uses three pointers (prev, curr, next) and rewires links one at a time. Recursive walks to the tail, then unwinds, flipping each pointer on the way back." 2. Write the iterative version first -- it is the canonical answer. 3. Write the recursive version next. 4. State complexities: iterative is O(n) time, O(1) space. Recursive is O(n) time, O(n) space due to the call stack. 5. Mention edge cases: empty list, single node. **Real LeetCode Example -- LC 206 (full code):** ```python theme={null} # Iterative -- preferred default def reverseList(head): prev, curr = None, head while curr: nxt = curr.next # save next BEFORE we overwrite curr.next curr.next = prev # flip the link prev = curr # advance prev curr = nxt # advance curr return prev # prev is the new head # Recursive -- elegant but uses O(n) call stack def reverseList_recursive(head): if not head or not head.next: return head new_head = reverseList_recursive(head.next) head.next.next = head # the next node now points back to us head.next = None # we become the tail return new_head ``` **Walkthrough for `1 to 2 to 3`:** * Iteration 1: prev=None, curr=1 -- save nxt=2, set 1.next=None, advance prev=1, curr=2. * Iteration 2: prev=1, curr=2 -- save nxt=3, set 2.next=1, advance prev=2, curr=3. * Iteration 3: prev=2, curr=3 -- save nxt=None, set 3.next=2, advance prev=3, curr=None. * Loop exits. Return prev=3. List is now `3 to 2 to 1`. **Senior follow-up 1**: "Can you reverse a linked list in groups of K (LC 25)?" Answer: yes -- reuse the iterative template as a subroutine. Outer loop walks K nodes ahead to confirm there are at least K to reverse. If yes, reverse in place and reconnect the previous group's tail to the new head. If fewer than K remain, leave them as-is. The trickiest part is the reconnection: keep a `group_prev` pointer to know where to attach the reversed segment. **Senior follow-up 2**: "Why does the recursive solution use O(n) space when there is no explicit data structure?" Answer: each recursive call allocates a stack frame. For a list of length n, the recursion goes n deep before unwinding. For very long lists (above 10K nodes in Python with default recursion limits), the recursive version stack-overflows. This is why production code virtually always uses the iterative form. **Senior follow-up 3**: "What if the linked list is doubly linked? Does reversal change?" Answer: for a true reversal, you swap the `prev` and `next` pointers of every node and then return the old tail as the new head. There is no need for a separate `prev` variable in the loop because each node already stores its predecessor. The complexity is still O(n) time, O(1) space, but the code is shorter. **Common Wrong Answers:** * "I would convert the list to an array, reverse the array, and rebuild the list." This is O(n) space and misses the entire point. It signals you have not internalized in-place pointer manipulation. * Writing the iterative version but forgetting to save `curr.next` before overwriting it. The list is silently truncated and you return a one-node list. * Recursive version that does not set `head.next = None` -- this leaves a cycle between the original head and its successor, producing infinite loops on traversal. **Further Reading:** * LC 92 (Reverse Linked List II) -- reverse only between positions L and R. * LC 25 (Reverse Nodes in K-Group) -- the natural extension. * LC 234 (Palindrome Linked List) -- uses reversal as a subroutine. **What interviewers are really testing:** Whether you understand Floyd's algorithm beyond rote memorization. Phase 2 (finding the cycle start) requires a non-obvious mathematical argument, and interviewers love asking candidates to derive it on the fly. **Strong Answer Framework:** 1. Phase 1: detect the cycle using fast/slow pointers. If they meet, a cycle exists. 2. Phase 2: reset one pointer to head. Move both at speed 1. They meet at the cycle start. 3. Justify phase 2 with the path-length argument: distance head to start equals distance meeting-point to start (mod cycle length). 4. State complexity: O(n) time, O(1) space. Beats the HashSet approach on space. **Real LeetCode Example -- LC 142 (full code):** ```python theme={null} def detectCycle(head): # Phase 1: detect the cycle slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # Phase 2: find the cycle start ptr = head while ptr is not slow: ptr = ptr.next slow = slow.next return ptr return None ``` **The math that makes Phase 2 work:** * Let `a` = distance from head to cycle start. * Let `b` = distance from cycle start to where slow and fast first meet. * Let `c` = remaining distance from meeting point back around to cycle start. * When they meet, slow has traveled `a + b`, fast has traveled `a + b + n*(b + c)` for some integer n (n times around the cycle). * Since fast moves 2x slow: `2(a + b) = a + b + n(b + c)`, which simplifies to `a = n(b + c) - b = (n-1)(b+c) + c`. * This means: walking `a` steps from head equals walking `c` steps plus some whole loops from the meeting point. So if we reset one pointer to head and walk both at speed 1, they meet exactly at the cycle start. **Senior follow-up 1**: "What is the length of the cycle once you have detected it?" Answer: after phase 1 detection, keep one pointer fixed at the meeting point and walk the other around until it returns. Count the steps. That is the cycle length, computed in O(C) where C is cycle length. Useful for problems that ask "how many nodes are in the cycle?" **Senior follow-up 2**: "Why is the meeting point not always the cycle start?" Answer: when slow first enters the cycle, fast is already somewhere inside it. They meet wherever the gap closes -- which depends on the relative position of fast at that moment. Only by chance is that the cycle entrance. The math in phase 2 corrects for this. **Senior follow-up 3**: "If fast moved 3 steps per iteration instead of 2, would the algorithm still work?" Answer: it would still detect cycles (fast still gains on slow), but the meeting point would be different, and the phase 2 reset would no longer land on the cycle start with a 1:1 walk. The 2:1 ratio is what makes the elegant `a = c (mod cycle)` identity hold. With 3:1, you would need different reset logic, and there is no clean closed form. **Common Wrong Answers:** * Storing visited nodes in a HashSet. Works but uses O(n) space -- the interviewer asked for O(1). * Hashing by value rather than identity. Two different nodes can have the same value but be distinct objects. The HashSet must key on object reference, not value. * Not handling the empty list or single-node-without-cycle edge case, which causes a null dereference in the first iteration. **Further Reading:** * LC 141 (Linked List Cycle) -- the simpler version: just detect, do not locate. * LC 287 (Find the Duplicate Number) -- Floyd's applied to an array via index-as-pointer. * LC 202 (Happy Number) -- Floyd's applied to a function-iteration sequence. **What interviewers are really testing:** Whether you can scale the simple two-list merge to K lists efficiently. They want to see two valid approaches with the same asymptotic complexity but different constant factors and implementation trade-offs. **Strong Answer Framework:** 1. State the brute force: sequential pairwise merge, O(k \* N) time. Acknowledge it works but is suboptimal. 2. Present approach A: min-heap of K heads. Pop, append, push that node's next. O(N log k) time, O(k) space. 3. Present approach B: divide-and-conquer pairwise merge. log k rounds, each doing O(N) work. O(N log k) time, O(log k) recursion stack. 4. Compare trade-offs: heap is easier to code and adapts to streams; D\&C has better cache locality for static input. **Real LeetCode Example -- LC 23 (heap solution, full code):** ```python theme={null} import heapq def mergeKLists(lists): heap = [] # Use index as tiebreaker because ListNode is not comparable for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy = ListNode(0) tail = dummy while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next ``` **Divide-and-conquer solution:** ```python theme={null} def mergeKLists(lists): if not lists: return None while len(lists) > 1: merged = [] for i in range(0, len(lists), 2): a = lists[i] b = lists[i + 1] if i + 1 < len(lists) else None merged.append(mergeTwo(a, b)) lists = merged return lists[0] def mergeTwo(l1, l2): dummy = ListNode(0) tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next = l1; l1 = l1.next else: tail.next = l2; l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 return dummy.next ``` **Cost analysis for N=1000 nodes spread across K=4 lists of 250 each:** * Sequential pairwise: round 1 merges 250+250=500 nodes. Round 2 merges 500+250=750. Round 3 merges 750+250=1000. Total: 2250 comparisons. * Heap: each node is pushed and popped once at O(log 4) = 2 cost. Total: 1000 \* 2 = 2000 operations. * Divide-and-conquer: round 1 merges 4 lists into 2 (each merge is 500 comparisons, 2 merges = 1000). Round 2 merges 2 into 1 (1000 comparisons). Total: 2000 comparisons. **Senior follow-up 1**: "What if K is huge (say, a million lists) but each list is tiny (a few nodes each)?" Answer: heap approach uses O(K) memory just for the heap, which becomes problematic. Divide-and-conquer is preferable because its recursion depth is O(log K) regardless of memory pressure. Alternatively, if the lists arrive as a stream, you cannot pre-build the heap and D\&C does not directly apply -- you would use a streaming heap with cap-K replacement. **Senior follow-up 2**: "How would you parallelize this for K very large?" Answer: divide-and-conquer is naturally parallel -- the K/2 pairwise merges in round 1 are independent and can run concurrently. Each subsequent round halves the parallelism. This is the same divide-and-conquer pattern used in parallel merge sort and is much harder to parallelize with the heap approach. **Senior follow-up 3**: "Why use a tiebreaker index in the Python heap?" Answer: when two nodes have equal values, Python's heapq compares the next element in the tuple. Without an index, it tries to compare the ListNode objects directly, which raises TypeError because ListNode does not implement `__lt__`. The index is a unique tiebreaker that ensures every tuple is comparable. **Common Wrong Answers:** * "Just merge them one by one." This is O(k \* N) -- repeatedly merging into the growing accumulator means early lists are re-traversed each time. * Using a max-heap and reversing at the end. Wastes time and signals confusion about heap direction. * Forgetting to push `node.next` after popping. The result is incomplete -- only the heads ever come out. **Further Reading:** * LC 21 (Merge Two Sorted Lists) -- the building block. * LC 378 (Kth Smallest Element in a Sorted Matrix) -- heap K-way merge applied to rows. * LC 632 (Smallest Range Covering Elements from K Lists) -- a variation using the same heap structure. **What interviewers are really testing:** Whether you can combine two data structures (HashMap and doubly linked list) to get O(1) on operations that individually would require O(n). This is one of the top three most-asked design questions at FAANG. **Strong Answer Framework:** 1. State the requirement: get and put both in O(1), eviction of least recently used on overflow. 2. Identify why a single data structure is not enough: HashMap has no order, linked list has no O(1) lookup. 3. Combine them: HashMap maps key to node reference; doubly linked list maintains usage order. 4. Use sentinel head and tail nodes to eliminate edge cases. 5. Walk through get and put step by step. **Real LeetCode Example -- LC 146 (full code):** ```python theme={null} class Node: def __init__(self, key, val): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = {} # key -> Node self.head = Node(0, 0) # sentinel: most recent end self.tail = Node(0, 0) # sentinel: least recent end self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): node.prev.next = node.next node.next.prev = node.prev def _add_front(self, node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self._remove(node) self._add_front(node) # mark as most recently used return node.val def put(self, key, value): if key in self.cache: self._remove(self.cache[key]) node = Node(key, value) self.cache[key] = node self._add_front(node) if len(self.cache) > self.capacity: lru = self.tail.prev # least recently used self._remove(lru) del self.cache[lru.key] ``` **Why a doubly linked list and not a singly linked list?** When you `get` a node, you need to remove it from its current position and move it to the head. Removing from the middle of a singly linked list requires finding the previous node, which is O(n). A doubly linked list lets you splice it out in O(1) using `node.prev` and `node.next`. **Why sentinel head and tail?** Without sentinels, every insert and remove has special cases for "is this the head or tail of the list?" Sentinels guarantee every real node has both a prev and a next, so the splice operations are uniform. **Senior follow-up 1**: "How would you make this thread-safe?" Answer: simplest is a single global lock around get and put, but that serializes all access. Better: shard the cache by hashing the key into N independent LRUs, each with its own lock -- reduces contention by N-fold. Best: read-write lock with batched recency updates -- reads append to a buffer that a background thread periodically replays under a write lock. Caffeine (Java) uses this. **Senior follow-up 2**: "What changes for LFU instead of LRU?" Answer: LFU evicts the least frequently used. You need a frequency count per node and a way to find the lowest frequency in O(1). The standard trick: a HashMap from frequency to a doubly linked list of nodes with that frequency, plus a `min_freq` tracker. On access, move the node from its current frequency list to the next-higher frequency list. On eviction, pull from the head of the `min_freq` list. This is LC 460. **Senior follow-up 3**: "Python has `collections.OrderedDict` which already does this. Could you implement LRU in 5 lines?" Answer: yes -- `OrderedDict.move_to_end(key)` on access and `popitem(last=False)` for eviction give the LRU semantics directly. Java's `LinkedHashMap` with `accessOrder=true` does the same. Mention this in interviews to demonstrate you know the standard library, but always be ready to implement from scratch since the interviewer is testing the underlying mechanics. **Common Wrong Answers:** * Using a singly linked list: O(n) per operation because you cannot splice in the middle in O(1). * Storing values directly in the HashMap with a separate list of keys: this works but you need to find a key in the list (O(n)) to remove it, defeating the design. * Forgetting to remove the evicted key from the HashMap: leads to a memory leak that grows unboundedly. **Further Reading:** * LC 460 (LFU Cache) -- the harder cousin. * LC 432 (All O(1) Data Structure) -- design a data structure with O(1) increment, decrement, getMaxKey, getMinKey. * "Design Data-Intensive Applications" by Martin Kleppmann, chapter on caching. ## Interview Questions **What interviewers are really testing:** Whether you understand the mathematical invariant behind Floyd's algorithm or just memorized the code. Candidates who truly get it can extend the reasoning to find the cycle start, calculate cycle length, or adapt the technique to other problems. **Strong Answer:** * Once both pointers are inside the cycle, think about the *relative distance* between them. Each iteration, fast gains exactly 1 step on slow (fast moves 2, slow moves 1, net gain = 1). So the gap shrinks by 1 every step -- it is impossible for fast to "jump over" slow because the gap decreases linearly from whatever it is down to 0. * More formally: if the cycle length is C and the gap between fast and slow when slow enters the cycle is `d`, they will meet after exactly `C - d` more iterations. This is O(n) because `d < C` and `C <= n`. * This is also why the algorithm works to *find the cycle start* in phase 2. Let the distance from head to cycle start be `a`, and the meeting point be `k` steps past the cycle start. The math shows `a = C - k`, so resetting one pointer to head and walking both at speed 1 makes them converge at the cycle entrance. * **Example:** In a list `1 -> 2 -> 3 -> 4 -> 5 -> 3` (cycle back to node 3), slow enters the cycle at node 3 while fast is already at node 5. Gap is 1 within the cycle (length 3). After 2 more steps (`C - gap = 3 - 1`), they meet at node 5. **Red flag answer:** "The fast pointer moves twice as fast so it will catch up eventually" -- this is hand-waving. It does not explain *why* fast cannot skip over slow, and the candidate cannot derive the cycle-start logic from first principles. **Follow-ups:** 1. If the fast pointer moved 3 steps per iteration instead of 2, would the algorithm still work? Under what conditions might it fail? 2. How would you modify Floyd's algorithm to return the *length* of the cycle after detecting it? **What interviewers are really testing:** Edge-case awareness and clean code instincts. Candidates who skip the dummy node often write buggy code with special-case `if head is None` or `if head == target` checks scattered everywhere. Interviewers want to see whether you proactively eliminate bug surface area. **Strong Answer:** * A dummy node is a fake node placed before the real head so that every real node, including the head, has a predecessor. This means operations like "delete a node" or "insert before a node" never need a special case for the head. * It is *essential* when the head itself might be removed (e.g., "remove all nodes with value X" where X is the head value), when merging two lists (either could provide the first element), or when reversing a sublist that starts at position 1. * It is *convenient but not strictly necessary* when you are only reading or traversing, like finding the middle node -- no pointers are being rewritten, so the head cannot change. * The cost is one extra allocation. In an interview setting, that is negligible. In a hot loop processing millions of lists in production (e.g., a custom allocator for network packet chains), you might avoid it and handle edge cases explicitly to save allocation overhead. * **Example:** In `remove_nth_from_end`, if `n` equals the list length, you are removing the head. Without a dummy node, you need `if fast is None after n steps, return head.next`. With a dummy node, the same loop logic handles it automatically -- zero special cases. **Red flag answer:** "I always use a dummy node because that is what the template says" -- no understanding of *why*, and no awareness of when it is unnecessary overhead. **Follow-ups:** 1. In a language without garbage collection (C/C++), what extra responsibility does the dummy node create, and how would you handle it? 2. Can you think of a linked list problem where using a dummy node actually makes the solution *harder* or more confusing? **What interviewers are really testing:** Whether you genuinely understand pointer manipulation or just memorized a template. The "what if you forget" part separates people who can debug linked list code on a whiteboard from those who cannot. **Strong Answer:** * The iterative reversal uses three variables: `prev`, `curr`, and `next_node`. Each iteration: (1) save `curr.next` into `next_node`, (2) set `curr.next = prev`, (3) advance `prev = curr`, (4) advance `curr = next_node`. * If you skip step 1 and go straight to `curr.next = prev`, you have just severed the link to the rest of the list. `curr.next` now points backwards, and you have no reference to the node that *was* next. The remaining tail of the list is leaked -- unreachable and lost. * Concretely: for `1 -> 2 -> 3`, if at node 2 you do `2.next = 1` without saving node 3 first, you now have `1 <- 2` and node 3 is floating in memory with nothing pointing to it. Your loop variable `curr` cannot advance because you have no saved reference to 3. * This is the single most common linked list bug in interviews. Drawing the pointer diagram before coding makes it almost impossible to make this mistake because you visually see that you are about to orphan a node. **Red flag answer:** Writes the reversal code from memory but cannot explain what breaks if a step is removed. Or says "it would cause an error" without specifying *what kind* of error (it is not a crash -- it is silent data loss, which is worse). **Follow-ups:** 1. How would you reverse a linked list recursively, and what is the space complexity difference compared to the iterative approach? 2. How do you reverse nodes in groups of K? Walk me through how the reversal subroutine plugs into the outer loop. **What interviewers are really testing:** Your ability to *compose* multiple linked list techniques into a single solution. This problem requires finding the middle (fast/slow), reversing the second half (iterative reversal), and comparing node by node -- three patterns chained together. It also tests whether you think about restoring the list afterward. **Strong Answer:** * Step 1: Use fast/slow pointers to find the middle of the list. For even-length lists, slow lands on the second middle node, which is exactly where the second half begins. * Step 2: Reverse the second half of the list in place starting from `slow`. * Step 3: Compare nodes from the head and from the reversed second-half head. If all values match, it is a palindrome. * Step 4 (production-grade, often missed): Reverse the second half *again* to restore the original list structure. In an interview, mentioning this earns bonus points because it shows you think about callers who still hold references to the list. * **Example:** For `1 -> 2 -> 3 -> 2 -> 1`: middle is node 3, reverse second half to get `1 -> 2 -> 3 <- 2 <- 1`. Compare: 1==1, 2==2, done -- palindrome confirmed. * Time: O(n) for finding middle + O(n/2) reversal + O(n/2) comparison = O(n). Space: O(1), only pointer variables. **Red flag answer:** "Copy the list into an array and check if the array is a palindrome." This is O(n) space and completely misses the point of the question. Or the candidate reverses the entire list instead of just the second half, destroying the structure. **Follow-ups:** 1. What changes if the list is doubly linked? Does the problem become trivial? 2. If the interviewer says "you must not modify the list at all," what is the best you can do for space complexity? **What interviewers are really testing:** Trade-off thinking. Both approaches work, but they have different space/time profiles. Interviewers want to see if you default to "whatever I memorized" or if you reason about constraints. **Strong Answer:** * **HashMap approach:** Store every visited node's reference (not value) in a set. If you encounter a node already in the set, there is a cycle. Time O(n), space O(n). Dead simple to implement and debug. * **Floyd's approach:** Two pointers, fast and slow. Time O(n), space O(1). More subtle to implement correctly but uses constant extra memory. * Choose HashMap when: you are debugging in production and want the simplest, most readable detection; memory is not constrained; you also want to record *which* nodes are in the cycle. * Choose Floyd's when: the list is enormous (millions of nodes) and you cannot afford O(n) extra memory; you are in an interview and the interviewer explicitly says "O(1) space"; or you also need to find the cycle start (Floyd's phase 2 gives this for free). * **Real-world example:** In a garbage collector's mark phase, cycle detection in object graphs uses techniques similar to Floyd's because allocating a HashMap proportional to the heap size would be self-defeating. * Subtle gotcha with HashMap: you must hash by *node identity* (memory address), not by *node value*. Two nodes can have the same value but be different nodes. In Python, the default `set` uses object identity for unhashable objects, but in Java you would use an `IdentityHashSet` or store references directly. **Red flag answer:** "Floyd's is always better because it uses O(1) space" -- ignoring that the HashMap approach is simpler, easier to debug, and sometimes preferable. Or not knowing that you must hash by identity, not value. **Follow-ups:** 1. Can you detect a cycle in a linked list using *no extra space at all* and *without modifying the list*? (Hint: think about what constraints make this theoretically impossible.) 2. If the list has no cycle but is 10 billion nodes long, which approach would you pick and why? **What interviewers are really testing:** Whether you can scale a simple pattern (merge two lists) to a harder problem, and whether you understand heap data structures and divide-and-conquer at a practical level. **Strong Answer:** * **Brute force -- merge one by one:** Merge list 1 and list 2, then merge the result with list 3, and so on. Time: O(k\*N) where N is total nodes, because early lists get re-traversed with each merge. This is the naive extension of "merge two sorted lists." * **Min-heap (priority queue):** Push the head of each list onto a min-heap. Pop the smallest, append it to the result, and push that node's `next` (if it exists). Time: O(N log k) because each of the N nodes is pushed/popped once, and heap operations are O(log k). Space: O(k) for the heap. * **Divide and conquer (pairwise merge):** Pair up the K lists and merge each pair. Repeat until one list remains. This is merge sort's merge phase applied to lists-of-lists. Time: O(N log k) -- same as the heap. Space: O(log k) for recursion stack if done recursively, or O(1) extra if done iteratively. * **When to pick which:** The heap approach is easier to code in an interview and handles dynamic streams well (new lists can be added). Divide-and-conquer has better cache locality and lower constant factors for static inputs. In practice, if K is small (say under 20), the brute-force sequential merge is fine and simplest to maintain. * **Example:** Merging 4 lists of 250 nodes each (1000 total). Heap: 1000 \* log(4) = 2000 operations. Pairwise: 2 rounds of merging -- round 1 merges 4 lists into 2 (500 comparisons each), round 2 merges 2 into 1 (1000 comparisons) = 2000 total. Sequential: round 1 = 500, round 2 = 750, round 3 = 1000 = 2250. Difference grows with K. **Red flag answer:** Only knows the heap approach and cannot explain the divide-and-conquer alternative, or says "just merge them one by one" without recognizing the O(k\*N) cost. **Follow-ups:** 1. If the K lists arrive as a stream (you do not know K upfront), which approach adapts best? 2. How would you implement the min-heap comparison in a language where list nodes are not natively comparable (e.g., Python's `heapq` with custom objects)? **What interviewers are really testing:** System design intuition applied to data structures. This bridges the gap between "can you manipulate pointers" and "can you design a data structure with specific performance guarantees." It is one of the most frequently asked FAANG problems. **Strong Answer:** * An LRU Cache needs two operations in O(1): `get(key)` and `put(key, value)`. On every access, the touched entry must move to the front (most recently used). On capacity overflow, the entry at the back (least recently used) must be evicted. * The HashMap gives O(1) lookup by key. The doubly linked list maintains the usage order -- head is most recent, tail is least recent. * **Why doubly linked?** When you access a node, you need to remove it from its current position and move it to the head. Removing a node from the middle of a singly linked list requires knowing the *previous* node, which means O(n) traversal to find it. A doubly linked list stores `prev` and `next`, so removal is O(1) -- just rewire `node.prev.next = node.next` and `node.next.prev = node.prev`. * The HashMap stores `key -> node_reference`, so you jump directly to the node without traversal. Combined with O(1) doubly-linked-list removal and insertion-at-head, both `get` and `put` are O(1). * **Production detail:** Python's `collections.OrderedDict` is literally a HashMap + doubly linked list under the hood. Java's `LinkedHashMap` with `accessOrder=true` does the same. In interviews, knowing this shows you understand that standard libraries already implement this pattern. **Red flag answer:** "Use a singly linked list and just search for the previous node when you need to remove" -- this is O(n) per operation, defeating the entire purpose. Or not knowing why the HashMap is needed alongside the list. **Follow-ups:** 1. How would you make this LRU Cache thread-safe? What are the concurrency pitfalls? 2. What changes if the requirement shifts from LRU to LFU (Least Frequently Used)? **What interviewers are really testing:** Your ability to handle a non-trivial pointer structure where a naive copy breaks because the random pointers reference nodes that may not exist yet in the copy. This tests both creativity and systematic thinking about object references. **Strong Answer:** * **Approach 1 -- HashMap (O(n) space):** First pass: iterate the original list, create a copy of each node, and store `original -> copy` in a HashMap. Second pass: iterate again and set each copy's `next` and `random` by looking up the corresponding originals in the map. Time O(n), space O(n). * **Approach 2 -- Interleaving (O(1) space):** This is the clever trick. Step 1: For each original node A, create copy A' and insert it right after A, so the list becomes `A -> A' -> B -> B' -> C -> C'`. Step 2: Set random pointers -- `A'.random = A.random.next` (because A.random's copy is always the next node after A.random). Step 3: Separate the interleaved list back into two lists. Time O(n), space O(1). * The interleaving approach is more complex to code and easier to get wrong, but it demonstrates a deeper understanding of pointer manipulation. In an interview, I would mention both approaches, implement the HashMap one first (correct and clean), and then explain the interleaving optimization if time permits. * **Key insight that most candidates miss:** In the HashMap approach, you must be careful that you are mapping *node references*, not node values. Two nodes can have the same value but are different objects with different random pointers. **Red flag answer:** Tries to copy nodes one at a time and set random pointers immediately -- this fails because the target of a random pointer might not have been copied yet. Or does not understand the difference between shallow copy and deep copy. **Follow-ups:** 1. If the list could contain cycles via the `random` pointers (not just the `next` pointers), does your HashMap approach still work? What about the interleaving approach? 2. How would you verify that your deep copy is correct? What test cases would you write? **What interviewers are really testing:** Whether you understand the theoretical complexity *and* the practical reality. Linked lists "win" on paper for insertions/deletions, but arrays often win in practice due to cache locality. This question separates textbook knowledge from systems-level understanding. **Strong Answer:** * **Insert at beginning:** Linked list O(1) -- create a node, point it to old head, done. Array O(n) -- shift every element right. Clear win for linked lists. * **Insert at middle (known position):** Linked list O(1) for the insertion itself *if you already have a pointer to the position*. But *finding* that position is O(n). Array O(n) for shifting. In practice, roughly equivalent unless you maintain pointers to strategic positions. * **Insert at end:** Linked list O(1) if you maintain a tail pointer, O(n) otherwise. Array O(1) amortized (dynamic array with doubling). Roughly equal. * **When linked lists actually win in practice:** When you are doing frequent insertions and deletions in the middle of a known position (e.g., an LRU cache where you hold a direct reference to the node). When the elements are large (moving large structs in an array is expensive). When you cannot tolerate worst-case O(n) pauses from array resizing. * **When arrays win despite worse theoretical complexity:** Almost everywhere else. CPU caches fetch contiguous memory in cache lines (typically 64 bytes). Arrays exploit this -- sequential access in an array is 10-100x faster than chasing pointers scattered across the heap. Bjarne Stroustrup (creator of C++) famously demonstrated that `std::vector` beats `std::list` even for insert-heavy workloads due to cache effects. * **Real-world example:** The Linux kernel uses intrusive linked lists extensively (via `list_head`) because they need O(1) removal of known elements from scheduler queues, and the elements are already heap-allocated for other reasons. **Red flag answer:** "Linked lists are better for insertions and deletions, arrays are better for access" -- this is the textbook one-liner that ignores cache locality, which is the dominant factor in modern hardware. **Follow-ups:** 1. What is an "intrusive" linked list, and why does the Linux kernel prefer it over a standard linked list? 2. If you are building a text editor's buffer, would you use an array, a linked list, or something else entirely? Why? **What interviewers are really testing:** Real debugging instincts with pointer-based data structures. Anyone can write linked list code from a template; this question reveals whether you can *fix* linked list code when it goes wrong -- a critical skill since pointer bugs do not throw helpful errors. **Strong Answer:** * **Step 1 -- Reproduce minimally:** Reduce the input to the smallest list that still triggers the bug. Usually 3-4 nodes is enough for linked list issues. Draw the list and all pointers on paper. * **Step 2 -- Trace pointer assignments:** Go through the code line by line on your minimal example. At each step, draw the state of every node's `next` pointer. The bug is almost always one of these: (a) you forgot to terminate a pointer with `null` after an operation, (b) you assigned `node.next` to a node that already appears earlier in the list, (c) you reused a variable that still points to a node from a previous iteration. * **Step 3 -- Check the usual suspects:** * After reversing a sublist, did you set the original head's `next` to null or to the correct successor? Forgetting this is the number-one cause of accidental cycles after partial reversals. * After merging, did the last node of one list still point to its old next instead of null? * When reordering (like the "reorder list" problem), the node that becomes the new tail must have its `next` set to null. * **Step 4 -- Add detection:** Temporarily add a Floyd's cycle check after your operation. If a cycle is detected, print the meeting point node's value -- this tells you which node's `next` pointer is wrong. * **Example:** In "Reorder List" (`1->2->3->4->5` becomes `1->5->2->4->3`), a common bug is not setting node 3's `next` to null after splitting and reversing the second half. Node 3 still points to node 4, but node 4 now points to node 3 (from the reversal), creating a `3 -> 4 -> 3` cycle. **Red flag answer:** "I would add print statements" -- vague and not linked-list-specific. Or "I would use a debugger" without explaining what you would actually look for. The best candidates have a systematic pointer-tracing methodology. **Follow-ups:** 1. In a language without garbage collection, how would an accidental cycle cause a memory leak, and how would you detect it? 2. You are reviewing a teammate's linked list code in a PR. What are the top 3 things you check for before approving? ## Interview Deep-Dive **What interviewers are really testing:** This problem requires three separate linked list techniques chained together -- finding the middle, reversing a sublist, and comparing two lists in lockstep. Candidates who cannot compose multiple patterns into a single solution struggle at the senior level. **Strong Answer:** * The approach has three phases. Phase 1: use the fast/slow pointer technique to find the middle of the list. When `fast` reaches the end, `slow` is at the midpoint. Phase 2: reverse the second half of the list starting from `slow`. Phase 3: compare the first half and the reversed second half node by node. If all values match, the list is a palindrome. * Critical detail: for even-length lists like `1 -> 2 -> 2 -> 1`, the slow pointer lands on the second `2` (the start of the second half). For odd-length lists like `1 -> 2 -> 3 -> 2 -> 1`, the slow pointer lands on `3` (the center node), and we can skip it during comparison because a single center element does not affect palindrome status. * After the comparison, a production-quality implementation should reverse the second half back to restore the original list structure. Interviewers notice whether you mention this -- it signals that you think about side effects and API contracts, not just solving the puzzle. * The space is O(1) because we reverse in-place and compare with two pointers. No array copy, no stack, no recursion. **Follow-up:** What if the linked list is doubly linked? Does this change your approach? **Follow-up Answer:** With a doubly linked list, the problem becomes trivial. You use two pointers starting at the head and tail, comparing values and moving inward. No reversal needed, no middle-finding needed. It reduces to the same logic as checking if a string is a palindrome with converging pointers. The time is still O(n), space is still O(1), but the code is about five lines instead of twenty. This is why interviewers specifically say "singly linked" -- they want to see if you can work without the backward pointer. **What interviewers are really testing:** This is one of the most frequently asked design questions at FAANG companies. It tests whether you can combine a doubly linked list with a HashMap to achieve O(1) for both access and eviction -- two operations that individually suggest different data structures. **Strong Answer:** * The core insight is that neither a HashMap nor a linked list alone is sufficient. A HashMap gives O(1) lookup by key but has no ordering. A doubly linked list maintains insertion/access order and supports O(1) removal (given a pointer to the node), but has O(n) lookup. Combining them gives both: the HashMap maps keys to list nodes, and the linked list maintains recency order. * On `get(key)`: look up the node in the HashMap in O(1). If found, move it to the front of the linked list (O(1) with a doubly linked list -- detach the node by updating its neighbors' pointers, then insert at the head). Return the value. * On `put(key, value)`: if the key already exists, update the value and move to front. If the key is new, create a node, insert at front, add to HashMap. If the cache exceeds capacity, evict the tail node (the least recently used), remove it from both the list and the HashMap. * Implementation detail that catches people: use a dummy head and dummy tail sentinel to avoid null-pointer edge cases when the list is empty or has one element. Without sentinels, insert and remove have multiple special cases. * This exact structure powers Memcached's internal slab allocator, Redis's approximate LRU, and most in-memory caches. **Follow-up:** What if you need thread-safe LRU for a concurrent web server? What changes? **Follow-up Answer:** The naive approach is a global lock around every get/put, but that serializes all cache access and destroys throughput under high concurrency. Better approaches: (1) Sharded LRU -- partition the key space into N independent LRU caches, each with its own lock. This reduces contention by N-fold. (2) Read-write lock -- allow concurrent reads (gets that do not promote) but exclusive writes. The problem is that `get` also modifies the list (moves to front), so it is actually a write. A common workaround is to batch recency updates: reads are lock-free and append to a buffer, a background thread periodically processes the buffer and updates the list under a write lock. This is what Caffeine (a Java caching library) does. (3) Lock-free approaches using CAS on the linked list pointers, though these are complex and rarely worth implementing from scratch. **What interviewers are really testing:** Whether you can analyze and compare two valid approaches for the same problem, articulating trade-offs rather than just picking one. This is a staff-level signal. **Strong Answer:** * **Heap approach:** Maintain a min-heap of size K containing one node from each list (the current head). Extract the minimum from the heap in O(log K), append it to the result, and push the next node from that list into the heap. Total time: O(N log K) where N is the total number of nodes across all lists. Space: O(K) for the heap plus O(1) for the output (reusing existing nodes). * **Divide-and-conquer approach:** Pair up the K lists and merge each pair using the standard two-list merge. This halves the number of lists. Repeat until one list remains. There are log K levels of merging, and at each level the total work across all pairs is O(N). Total time: O(N log K). Space: O(log K) for the recursion stack, O(1) extra for the merges (in-place pointer manipulation). * Both are O(N log K) time, but the constants differ. The heap approach has overhead from heap operations (sift-up, sift-down, comparison functions, potential cache misses from pointer chasing in the heap). The divide-and-conquer approach performs simple sequential pointer operations that are more cache-friendly. * In practice, divide-and-conquer tends to be faster for linked lists because the merge step is purely sequential pointer manipulation with excellent locality. The heap approach is simpler to code and better when you need a streaming solution (processing elements one at a time as they arrive). * Edge case both must handle: empty lists in the input. The heap approach naturally handles this (just do not push null nodes). The divide-and-conquer approach handles it via the base case of the two-list merge. **Follow-up:** If the lists were not linked lists but sorted arrays, would your recommendation change? **Follow-up Answer:** Yes. With sorted arrays, the heap approach becomes more attractive because extracting elements from arrays is sequential memory access (good cache behavior), and the merge step in divide-and-conquer requires allocating temporary arrays (O(N) extra space) since you cannot rewire pointers like with linked lists. For arrays, a K-way merge using a heap with O(K) space is often the pragmatic choice. This is exactly what external merge sort does when merging sorted runs from disk -- a min-heap of K file pointers, each pointing to the next unread element from a sorted run. **What interviewers are really testing:** This problem has an elegant two-pointer solution that most candidates do not see immediately. It tests creative pointer manipulation and mathematical reasoning about path lengths. **Strong Answer:** * The elegant approach: start two pointers, one at each list head. Advance both one step at a time. When a pointer reaches the end of its list, redirect it to the head of the other list. If the lists intersect, the two pointers will meet at the intersection node. If they do not intersect, both pointers will reach null simultaneously. * Why it works: let list A have length `a` (before intersection) + `c` (shared tail), and list B have length `b` + `c`. Pointer A travels `a + c + b` steps before reaching the intersection on its second pass. Pointer B travels `b + c + a` steps. Since `a + c + b = b + c + a`, they arrive at the intersection at the same time. * If there is no intersection, pointer A travels `a + c + b + c` and pointer B travels `b + c + a + c`. Wait -- actually for the no-intersection case, pointer A travels `a + b` total and pointer B travels `b + a` total, both reaching null at the same moment. So the null check naturally handles the no-intersection case. * Alternative approach: compute the lengths of both lists. Advance the longer list's pointer by the length difference. Then walk both in lockstep until they meet. Same O(n) time, O(1) space, but requires two passes. **Follow-up:** Why can two singly linked lists not intersect and then diverge (form an X-shape rather than a Y-shape)? **Follow-up Answer:** Because each node has exactly one `next` pointer. Once two lists share a node, that node's `next` is a single pointer to the same subsequent node. They can never split apart. The shared portion is always a suffix, forming a Y-shape. This is a fundamental structural property of singly linked lists and is why the "intersection" problem is well-defined. In a doubly linked list, the same constraint applies -- each node has one `next` and one `prev`, so the structure cannot diverge once merged. Only in a graph (where nodes can have multiple outgoing edges) could two paths merge and then split.