Linked List
Concept
A Linked List is a chain of nodes where each node holds a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory โ you can only access elements by following pointers from the head.
// Standard ListNode definition (used in all LeetCode problems)
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
Key property: Insertions and deletions are O(1) if you have a pointer to the location โ but finding that location is O(n).
When to Use
- Problem explicitly gives you a
ListNode - Need O(1) insert/delete at a known position
- Cycle detection (Floyd's algorithm)
- Reversing a sequence in-place
- Merge operations on sorted sequences
Core Techniques
1. Dummy Head Node
Eliminates edge cases when inserting/deleting from the head:
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// ... manipulate list ...
return dummy.next; // new head
2. Fast & Slow Pointers
Slow moves 1 step, fast moves 2 steps. Used for:
- Finding the middle node
- Detecting cycles
- Finding the k-th from end node
// Find middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is now at middle
3. In-Place Reversal
public ListNode reverse(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev; // new head
}
Worked Example 1: Detect and Return Cycle Start
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// Phase 1: Detect if cycle exists
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break; // they meet inside the cycle
}
// No cycle
if (fast == null || fast.next == null) return null;
// Phase 2: Find cycle start
// Move one pointer back to head; advance both one step at a time
// They meet at the cycle entry point
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
Why does Phase 2 work? If the distance from head to cycle start is d, and the cycle length is c, then after phase 1 the meeting point is exactly c - (d % c) steps from the cycle start โ and advancing one pointer from head by d steps lands both at the cycle start simultaneously.
Worked Example 2: Merge K Sorted Lists
public ListNode mergeKLists(ListNode[] lists) {
// Use a min-heap ordered by node value
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
(a, b) -> a.val - b.val
);
// Add the head of each list
for (ListNode node : lists) {
if (node != null) minHeap.offer(node);
}
ListNode dummy = new ListNode(0), curr = dummy;
while (!minHeap.isEmpty()) {
ListNode smallest = minHeap.poll();
curr.next = smallest;
curr = curr.next;
if (smallest.next != null) minHeap.offer(smallest.next);
}
return dummy.next;
}
Time: O(N log k) where N = total nodes, k = number of lists
Worked Example 3: Reverse Nodes in k-Group
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
// Find the k-th node from groupPrev
ListNode kth = getKth(groupPrev, k);
if (kth == null) break;
ListNode groupNext = kth.next;
// Reverse group
ListNode prev = groupNext, curr = groupPrev.next;
while (curr != groupNext) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Reconnect
ListNode tmp = groupPrev.next; // old first = new last in group
groupPrev.next = kth;
groupPrev = tmp;
}
return dummy.next;
}
private ListNode getKth(ListNode curr, int k) {
while (curr != null && k > 0) {
curr = curr.next;
k--;
}
return curr;
}
Worked Example 4: Design LRU Cache (LeetCode #146)
Problem: Design a data structure that implements get(key) and put(key, value) with time complexity, evicting the least recently used item when reaching capacity.
Approach: Combine a HashMap<Integer, Node> (for lookup) with a Doubly Linked List (for node deletion and insertion at the head).
class LRUCache {
class Node {
int key, val;
Node prev, next;
Node(int k, int v) { this.key = k; this.val = v; }
}
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node);
insertAtHead(node);
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
remove(map.get(key));
}
if (map.size() >= capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
Node node = new Node(key, value);
insertAtHead(node);
map.put(key, node);
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insertAtHead(Node node) {
node.next = head.next;
node.next.prev = node;
head.next = node;
node.prev = head;
}
}
Time: for get and put | Space:
LeetCode Problems
Easy
| # | Problem | Technique |
|---|---|---|
| 21 | Merge Two Sorted Lists | Dummy head |
| 83 | Remove Duplicates from Sorted List | Single pass |
| 141 | Linked List Cycle | Fast/Slow |
| 160 | Intersection of Two Linked Lists | Length equalization |
| 206 | Reverse Linked List | In-place reversal |
| 234 | Palindrome Linked List | Find mid + reverse |
Medium
| # | Problem | Technique |
|---|---|---|
| 2 | Add Two Numbers | Carry simulation |
| 19 | Remove Nth Node From End | Two pointers, n-gap |
| 61 | Rotate List | Find new tail |
| 82 | Remove Duplicates II | Dummy head |
| 86 | Partition List | Two dummy heads |
| 92 | Reverse Linked List II | Partial reversal |
| 138 | Copy List with Random Pointer | HashMap / interleave |
| 142 | Linked List Cycle II | Floyd's phase 2 |
| 143 | Reorder List | Find mid + reverse + merge |
| 148 | Sort List | Merge sort on list |
Hard
| # | Problem | Technique |
|---|---|---|
| 23 | Merge K Sorted Lists | Min-heap |
| 25 | Reverse Nodes in k-Group | Group reversal |