Linked Lists
Linked lists store elements as nodes connected by pointers, allowing O(1) insertions and deletions at any position if you have a reference to it. Linked list problems test your ability to manipulate pointers carefully without losing references. The fast-and-slow pointer (Floyd's cycle detection) technique is a key pattern that extends beyond lists to any sequence with possible cycles.
When to Use
- →You need to reverse, merge, or reorder a sequence of nodes
- →You need to detect cycles in a linked structure
- →You need to find the middle element or kth-from-end node efficiently
- →You need to manipulate nodes in-place without extra space
- →You need to merge multiple sorted sequences
Approach
For reversal problems, maintain three pointers: previous, current, and next. At each step, save the next node, point current's next to previous, then advance. This iterative approach is cleaner than recursion for full reversal.
The fast-and-slow pointer technique uses two pointers moving at different speeds. For cycle detection, the fast pointer moves two steps while the slow moves one — they'll meet inside the cycle if one exists. For finding the middle node, when the fast pointer reaches the end, the slow pointer is at the middle.
For merge problems (like merge k sorted lists), use a divide-and-conquer approach or a min-heap. Merge two lists by comparing their heads and appending the smaller one. Always use a dummy head node to simplify edge cases where the head of the result is unknown.
Code Template
// Reverse a 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;
}
// Detect cycle (Floyd's algorithm)
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;
}
// Merge two sorted lists
function mergeTwoLists(l1, l2) {
const dummy = { next: null };
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}