Gap / alignment (Linked List — Fast & Slow Sub-pattern)
Both pointers move at the same speed, but one starts ahead (by n nodes, or by the difference in the lists' lengths), so they reach the target at the same moment.
- ›
"n-th node from the end"
- ›
"remove / swap the k-th node from the end"
- ›
"the node where two lists intersect"
Remove Nth Node From End uses a dummy and a gap of n + 1 so slow stops before the node to unlink. Intersection of Two Linked Lists aligns two lists of different lengths: either skip the length difference in the longer one first, or let each pointer jump to the other list's head when it ends — both then walk m + n and meet at the shared node (or both reach null). Swapping Nodes walks k − 1 steps to the k-th node, then uses it as the head start: move it and a second pointer from the head until the first one is on the last node (not null), so the second stands on the k-th from the end. Swap the two values; no relinking needed.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Remove Nth Node From End of ListWalkthroughMediumBasic Anchor·LeetCode #19
- 2Intersection of Two Linked ListsWalkthroughEasyBasic Reinforcement·LeetCode #160
- 3Swapping Nodes in a Linked ListWalkthroughMediumSlight Variation·LeetCode #1721
Template
// Remove the n-th node from the end in one pass.
// fast goes n + 1 steps ahead of slow; when fast hits null, slow is just BEFORE the target.
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head); // dummy: removing the head is not a special case
ListNode *slow = &dummy, *fast = &dummy;
for (int i = 0; i <= n; i++) fast = fast->next; // gap of n + 1
while (fast) { slow = slow->next; fast = fast->next; }
ListNode* target = slow->next;
slow->next = target->next; // unlink it
delete target;
return dummy.next;
}