Pattern GuideLinked Lists
Algorithm Pattern

Linked Lists

"A node only knows what it points to. Manage your pointers carefully."

15 min read
Fundamental
Space: O(1)
01
THE CORE INTUITION

The absolute basics: Linked Lists

🔗

Mental Model

Arrays are fast at reading data because they store everything in a single, perfectly lined-up block of memory. But inserting at the front means shifting every single element — O(N).

Linked Lists solve this by sacrificing contiguous memory. Data lives in independent Nodes scattered across memory, connected by pointers. Insertion is O(1) — just update two pointers instead of shifting everything.

Why Linked Lists are fast for insertion: Because the items aren't physically locked next to each other. You create a new Node anywhere and tell surrounding items to update their pointers. It's an instant change!

Array: Head Insert
1
2
3
4

Data Shifting Required: O(N)

Linked List: Head Insert
+
1
2
3

Only 1 Pointer Changes: O(1)

Array: arr[4]
0
1
2
3
4
5

Direct Memory Jump: O(1)

Linked List: Node 4
0
1
2
3
4
5

Sequential Traversal: O(N)

02
IMPLEMENTATION

Creating and Accessing a Linked List

A ListNode is just an object with a val and a next pointer. To build a list, link nodes together. To access elements, loop until null.

ListNode.js
1
class ListNode {
2
constructor(val = 0, next = null) {
3
this.val = val;
4
this.next = next;
5
}
6
}
7
8
// Build: (1) -> (2) -> (3) -> null
9
const head = new ListNode(1);
10
head.next = new ListNode(2);
11
head.next.next = new ListNode(3);
12
13
// Traversal
14
let curr = head;
15
while (curr !== null) {
16
console.log(curr.val);
17
curr = curr.next;
18
}

Dynamic Visualizer: Core Operations

1234

O(N): Traversing node by node to find the target. No direct index.

03
BLUEPRINTS

In-Place Reversal

The 3-Pointer Dance

Reverse direction without using extra memory by flipping arrows as you go. Save next → reverse → shift.

  • Save curr.next before breaking it
  • Reverse the arrow: curr.next = prev
  • Shift both pointers forward
  • Return prev as the new head
reverseList.js
1
function reverseList(head) {
2
let prev = null;
3
let curr = head;
4
5
while (curr !== null) {
6
const next = curr.next; // 1. Save future
7
curr.next = prev; // 2. Reverse arrow
8
prev = curr; // 3. Shift prev
9
curr = next; // 4. Shift curr
10
}
11
12
return prev; // New head
13
}
04
BLUEPRINTS

Dummy Node Strategy

The Safe Anchor

Provides a safe anchor when the head might change or is created dynamically. Prevents null-pointer edge cases.

  • Create a dummy node (value doesn't matter)
  • Attach new nodes to tail.next
  • Return dummy.next — skips the anchor
  • Essential for merging, partitioning, removal
mergeTwoLists.js
1
function mergeTwoLists(list1, list2) {
2
const dummy = new ListNode(0);
3
let tail = dummy;
4
5
while (list1 !== null && list2 !== null) {
6
if (list1.val < list2.val) {
7
tail.next = list1;
8
list1 = list1.next;
9
} else {
10
tail.next = list2;
11
list2 = list2.next;
12
}
13
tail = tail.next;
14
}
15
16
tail.next = list1 ?? list2;
17
return dummy.next; // Skip the dummy head
18
}
05
FLAVOR

Fast & Slow Pointers

A linked list has no indices, so you can't jump to "the middle" or check "does this loop back on itself" directly. Move two pointers at different speeds instead — one step at a time (Slow) and two at a time (Fast). When Fast reaches the end, Slow is at the middle. If the list has a cycle, Fast eventually laps Slow from behind.

hasCycle.js
1
function hasCycle(head) {
2
let slow = head, fast = head;
3
while (fast && fast.next) {
4
slow = slow.next;
5
fast = fast.next.next;
6
if (slow === fast) return true; // they collided — cycle!
7
}
8
return false; // fast fell off the end — no cycle
9
}
middleNode.js
1
function middleNode(head) {
2
let slow = head, fast = head;
3
while (fast && fast.next) {
4
slow = slow.next;
5
fast = fast.next.next;
6
}
7
return slow; // fast hit the end — slow is the middle
8
}
See the full animated cycle-detection & middle-finding walkthrough
06
CAUTION

Common Pitfalls

Losing the Future

When reversing arrows, doing curr.next = prev before saving the original curr.next loses the rest of the list. Always cache next first.

Forgetting a Dummy Node

Deleting the head node is a special case — there's no "previous" node to re-point. A dummy node placed before head removes this special case entirely, so head-deletion and middle-deletion use identical code.

Losing the Tail While Appending

Building a list by repeatedly walking from head to find the last node turns every append into O(N). Keep a running tail pointer so appends stay O(1).

Comparing Nodes vs Values

slow === fast checks if they're the same node (pointer identity) — this is what cycle detection needs. slow.val === fast.val checks equal values, which two different nodes can share and gives a false positive.

07
RECOGNITION

How to Spot This Pattern

🔎 "Restructure the list in place" with O(1) extra space.

🔎 "Reverse in groups of K" or "reverse between positions."

🔎 "Merge" two or more already-sorted lists.

🔎 "Nth node from the end" — a two-pointer gap, no length pre-count needed.

Reverse Linked ListEasy
Merge Two Sorted ListsEasy
Remove Nth Node From EndMedium
Linked List CycleEasy

"Save the future, break the present, and move into the past."