Linked List Fundamentals — Pointers with Purpose
Demystify singly and doubly linked lists, pointer manipulation, and fast/slow patterns that dominate interview questions.
Problem Statement
Understand how linked lists store nodes, how to traverse and mutate them safely, and how to apply two-pointer techniques to solve classic problems.
Why This Problem Matters
- Linked lists test pointer literacy—boundary handling, dummy heads, and cycle detection all appear in interviews.
- They underpin stacks, queues, and adjacency lists (graph modeling).
- Two-pointer techniques (fast/slow) rely on understanding the underlying structure.
Thought Process
Normalise list construction with dummy nodes
Dummy heads simplify insertion and removal logic by avoiding special cases for the first node.
Use fast/slow pointers for cycle detection and middle finding
Advance fast two steps and slow one step; if they meet, a cycle exists.
Articulate memory and traversal trade-offs
Linked lists excel at O(1) insertions/removals but cost O(n) to access arbitrary indices—say that explicitly.
Step-by-Step Reasoning
- Define a Node class with value and next (optionally prev).
- Traverse using a pointer variable, advancing pointer = pointer.next.
- Use a dummy node when inserting/removing to handle head updates gracefully.
- Leverage fast/slow pointers for cycle checks, middle elements, or palindrome validation.
Dry Run
List 1 → 2 → 3 → 4, insert 5 after 2
Using a dummy head, traverse to node 2, set newNode.next = node2.next, node2.next = newNode. Structure becomes 1 → 2 → 5 → 3 → 4.
Cycle detection
fast pointer reaches back to meet slow pointer inside the loop, confirming a cycle.
Complexity Analysis
Time
O(n) for traversal
Space
O(1)
Why
Traversing the list touches each node once with constant extra memory.
Annotated Solution
public class LinkedListUtils {
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}
}Reversal is a staple pattern. Narrate pointer pivots carefully to prove you understand mutation without losing access.
Common Pitfalls
- Forgetting to store nextNode before rewiring pointers causes data loss.
- Not resetting prev/current properly when reversing leads to cycles or null dereferences.
- Ignoring null checks at boundaries leads to runtime exceptions.
Follow-Up Questions
- Implement a doubly linked list with O(1) insert/delete using prev pointers.
- Describe how to detect the start of a cycle using Floyd’s algorithm.
- Combine linked list reversal with slow/fast pointers to check if a list is a palindrome.