Mock 2 — Linked Lists (45 min)

# Mock 2 — Linked Lists ## The brief Three linked-list problems. Linked lists test pointer manipulation — a different muscle from array manipulation. ## Setup ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` ## Problem 1 — Reverse a Linked List (Easy, ~10 min) Reverse a singly linked list. Return the new head. ``` Input: 1 → 2 → 3 → 4 → 5 Output: 5 → 4 → 3 → 2 → 1 ``` ### Approach script 1. State: "Reverse the direction of pointers." 2. Iterative: "Three pointers: prev, curr, next. At each step, save next, point curr to prev, advance prev and curr. Returns prev at end." 3. Recursive: "Reverse the rest; point current's next.next back to current; clear current.next." 4. Compare: iterative is O(1) space; recursive is O(N) stack. ### Solution (iterative) ```python def reverse_list(head): prev = None curr = head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev ``` ## Problem 2 — Detect Cycle (Medium, ~15 min) Determine if a linked list has a cycle. Bonus: return the start of the cycle. ``` 1 → 2 → 3 → 4 → 5 → 2 (cycle: 5 points back to 2) Answer: cycle detected, starts at 2 ``` ### Approach script 1. State: "Detect if there's a cycle; find where it starts." 2. Naive: "Hashset of visited nodes. O(N) space." 3. Floyd's algorithm: "Fast pointer moves 2 steps, slow moves 1. If they meet, there's a cycle. After they meet, move slow to head; both advance 1 step; they meet at cycle start. O(1) space." 4. Math intuition: when they meet inside the cycle, the distance from head to cycle-start equals the distance from meeting point to cycle-start (modulo cycle length). ### Solution ```python def detect_cycle(head): if not head: return None slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # Cycle found; find start slow = head while slow != fast: slow = slow.next fast = fast.next return slow return None ``` ## Problem 3 — Merge K Sorted Lists (Hard, ~20 min) Merge K sorted linked lists into one sorted list. ``` Input: [[1,4,5], [1,3,4], [2,6]] Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 ``` ### Approach script 1. State: "Merge K sorted lists into one sorted list." 2. Naive: "Concatenate all, sort. O(NK log NK)." 3. Pairwise merge: "Merge two at a time. O(NK log K) — better." 4. Heap-based: "Heap of head pointers; pop the smallest, advance its list, push next. O(NK log K). Same big-O as pairwise but cleaner." 5. Walk through the heap approach. ### Solution ```python import heapq def merge_k_lists(lists): h = [] for i, lst in enumerate(lists): if lst: heapq.heappush(h, (lst.val, i, lst)) dummy = ListNode() tail = dummy while h: val, i, node = heapq.heappop(h) tail.next = node tail = node if node.next: heapq.heappush(h, (node.next.val, i, node.next)) return dummy.next ``` Note: the `(val, i, node)` tuple — `i` is a tiebreaker because nodes aren't comparable. ## Self-rubric - [ ] All 3 solved correctly - [ ] Reverse: O(1) extra space (iterative) - [ ] Cycle: Floyd's O(1) space, not hashset - [ ] Merge K: O(NK log K) - [ ] Drew the linked list diagram before coding cycle detection ## Deliverables - Solutions. - Trace through Floyd's on a small cycle example, showing where slow and fast meet.