Question Bank
Linked List Trace and Pointers
Difficulty: Medium
Four mid-level prompts on in-place reversal, node swapping, and the trickiest pointer bug. Mixes implementation and step-by-step trace.
Linked List Trace and Pointers
Four mid-level prompts on in-place reversal, node swapping, and the trickiest pointer bug. Mixes implementation and step-by-step trace.
340 views
4
Implement reverseList(head) that reverses a singly linked list in place and returns the new head. Use the iterative three-pointer pattern.
Examples
Example 1:
Input: head = 1 -> 2 -> 3 -> null
Output: new head with traversal yielding [3, 2, 1]
Explanation: Maintain prev = null and curr = head. Each step saves next = curr.next, redirects curr.next = prev, then advances prev and curr. The save step is what prevents losing the rest of the list. O(n) time, O(1) space.Implement swapPairs(head) that swaps every two adjacent nodes (1 -> 2 -> 3 -> 4 becomes 2 -> 1 -> 4 -> 3). Aim for an iterative O(1)-space solution using a dummy head.
Examples
Example 1:
Input: head = 1 -> 2 -> 3 -> 4 -> null
Output: traversal yields [2, 1, 4, 3]
Explanation: Use a dummy head plus a prev pointer. While the next two nodes (a, b) exist, rewire prev.next = b, a.next = b.next, b.next = a, then advance prev = a. Node references move (not just values).Trace it. Walk through reverseList(1 -> 2 -> 3 -> null) and list prev, curr, next after each iteration of the loop in the standard iterative reversal.
Examples
Example 1:
Input: head = 1 -> 2 -> 3 -> null
Output: returns node(3); traversal yields [3, 2, 1]
Explanation: Iter 1: save next = node(2), set node(1).next = null, advance prev = node(1), curr = node(2). Iter 2: save next = node(3), set node(2).next = node(1), advance. Iter 3: save next = null, set node(3).next = node(2). Loop exits, returns node(3).Spot the bug. removeAt(head, k) should remove the k-th node (0-indexed) and return the new head. The version below corrupts the list when k === 0.
Examples
Example 1:
Input: head = 1 -> 2 -> 3, k = 0
Output (buggy version): throws because prev is null
Output (fixed version): new head 2 -> 3
Explanation: When k = 0 the loop never runs and prev stays null. The clean fix prepends a dummy node so the boundary case at index 0 reuses the same code path as the middle of the list.