Pointer manipulation, cycle detection, reversal, and merge operations.
A linked list is a sequence of nodes where each node holds data and a pointer to the next node. Key patterns are the dummy head node, two-pointer gap, fast/slow pointers, and in-place reversal.
Traversal O(n) · Insert/Delete at known node O(1)
O(1) pointer manipulation, O(n) hash map approaches
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this whenever you might need to delete or modify the head of the list, because without a dummy you need messy special cases for the very first node
By prepending a dummy node, every real node including the head has a predecessor and your pointer logic stays uniform. This is one of the most important linked list tricks.
Problem Remove Nth Node From End. Attach a dummy before head, run the two-pointer gap, then unlink the target node.
// Dummy head — Remove Nth Node From End of List
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0);
dummy.next = head;
let fast = dummy, slow = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast) { slow = slow.next; fast = fast.next; }
slow.next = slow.next.next;
return dummy.next;
}Use this when you need to find the middle of a list, detect a cycle, or find where a cycle begins
The slow pointer advances one step at a time while the fast pointer advances two steps. If they meet, a cycle exists. If fast reaches null first, the list is cycle-free. The middle is found when fast reaches the end.
Problem Linked List Cycle. Move slow by one and fast by two; if they ever reference the same node, a cycle was detected.
// Fast/slow pointers — Linked List Cycle detection
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Use this when you need to locate a node relative to the end of the list in a single pass
Advance the first pointer k steps ahead, then move both pointers together at the same speed. When the lead pointer reaches the end, the trailing pointer is exactly where you need it.
Problem Remove Nth Node From End. The slow pointer lands just before the target node after the gap traversal, allowing O(1) deletion.
// Two-pointer gap — find middle of linked list
function findMiddle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow is now at middle
}Use this when you need to reverse a linked list or a segment of it without using extra space
The trick is to use three pointers: prev, curr, and next. At each step, redirect curr.next to prev, then advance all three pointers. This is an entirely pointer-manipulation approach with no extra nodes.
Problem Reverse Linked List. Iterate through the list, reversing each next pointer to point backwards.
// In-place reversal — Reverse Linked List
function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}Use this when two already-sorted lists need to be combined in order
Start a dummy head and a current pointer, then at each step compare the front values of both lists and attach the smaller one. This produces the merged list in one pass without any extra allocation beyond the existing nodes.
Problem Merge Two Sorted Lists. Repeatedly advance the pointer on whichever list has the smaller current value.
// Merge two sorted lists — dummy head + two pointers
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 ?? l2;
return dummy.next;
}Use this when the list contains extra pointers such as a random pointer that reference arbitrary nodes, making order-based copying impossible
Build a map from each original node to its freshly created copy first, then wire up the next and random pointers in a second pass. This keeps the logic clean and runs in O(n) time and space.
Problem Copy List with Random Pointer. First pass creates all new nodes; second pass assigns next and random using the map.
// Hash map deep copy — Copy List with Random Pointer
function copyRandomList(head) {
const map = new Map();
let curr = head;
while (curr) { map.set(curr, new Node(curr.val)); curr = curr.next; }
curr = head;
while (curr) {
if (curr.next) map.get(curr).next = map.get(curr.next);
if (curr.random) map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}