Linked Lists
Practice & Revision
Linked List pattern recognition decision tree, cheat sheet, and Top 15 must-solve linked list interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Linked Lists. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Linked List Pattern Decision Tree
Use this guide to identify which pointer strategy or pattern fits your problem constraints:
3. Revision Cheat Sheet
Common Pointer Operations Invariants
| Operation | Implementation Invariant | Visual Re-wiring Action |
|---|---|---|
| Reverse List | prev=null, curr=head | nxt=curr.next; curr.next=prev; prev=curr; curr=nxt; |
| Middle Node | slow=head, fast=head | while(fast && fast.next) { slow=slow.next; fast=fast.next.next; } |
| Cycle Detection | slow=head, fast=head | if(slow == fast) -> cycle exists |
| Dummy Head | dummy.next=head, curr=dummy | Eliminates null pointer checks when deleting head node |
| Linked List Merge | Compare current nodes | curr.next = (l1.val <= l2.val) ? l1 : l2; curr = curr.next; |
4. Top 15 Must-Solve Linked List Problems
5. Problem-Solving Framework
When coding pointer manipulation, follow this 3-step checklist:
1. Draw the State Transitions:
- Write out variable nodes prev, curr, and next on paper. Trace how pointer reassignments affect references.
2. Handle Null Boundary Checks:
- Always check if curr or curr.next is null before accessing .val or .next.next to avoid crash exceptions.
3. Use the Dummy Head Pattern by Default:
- If the output list's head might be swapped, deleted, or shifted, create a dummy node pointing to head and return dummy.next as your result.
6. Quiz
Question 1: In the 'Palindrome Linked List' problem, how do we compare both halves in O(1) auxiliary space?
Answer: We find the middle of the list using fast/slow pointers. We reverse the second half of the list in-place. We then compare the values of the first half (from head) and reversed second half element-by-element. Optionally, we reverse the second half back to restore the original list structure.Question 2: What is the benefit of the 'Gap-Two Pointer' pattern in removing the N-th node from the end?
Answer: We advance afast pointer N + 1 steps from a dummy node, leaving slow at the dummy. We then advance both pointers 1 step at a time. When fast reaches null, the slow pointer sits exactly at the node preceding the target N-th node from the end, allowing us to delete the target node in O(1) time.
Question 3: In C++, why must we be careful when merging lists in-place?
Answer: We must not delete nodes that are still linked as part of the other list. Simply re-linking pointer values is safe, but we must make sure not to create circular loops that lead to infinite cycles or memory leaks.Question 4: What is the optimal time complexity to reverse nodes in k-Group?
Answer:O(N) time. We scan the list to check if at least K nodes exist. If yes, we reverse the group in-place in O(K) time and recursively process the remaining list.
Question 5: What occurs if we attempt to find a cycle start node using Floyd's algorithm on a straight list?
Answer: The fast pointer will reachnull or its next will be null, the detection loop will terminate and return null immediately, indicating no cycle exists.