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.// class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
function reverseList(head) {
// TODO: iterative reversal with prev / curr / next
}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).function swapPairs(head) {
// TODO: dummy head + pointer surgery, no value swap
}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).function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}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.function removeAt(head, k) {
let prev = null, curr = head;
let i = 0;
while (curr && i < k) {
prev = curr;
curr = curr.next;
i++;
}
if (curr) prev.next = curr.next;
return head;
}