Why Linked Lists Are Tested
Linked lists appear in roughly 10% of coding interviews, mostly testing pointer manipulation, two-pointer techniques, and recursive thinking. The problems rarely require complex algorithms — the challenge is careful pointer bookkeeping and avoiding null pointer errors. LRU cache implementation (a linked list combined with a hash map) is a high-frequency senior interview question.
Core Operations
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Reverse a linked list (iterative)
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev # new head
# Reverse a linked list (recursive)
def reverse_recursive(head):
if not head or not head.next:
return head
new_head = reverse_recursive(head.next)
head.next.next = head # make next node point back
head.next = None
return new_head
Pattern 1: Fast and Slow Pointers
Two pointers moving at different speeds solve cycle detection and midpoint finding in one pass.
# Detect cycle (Floyd cycle detection)
def has_cycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Find cycle start node
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast:
break
else:
return None # no cycle
# Move one pointer to head; advance both at same speed
slow = head
while slow != fast:
slow, fast = slow.next, fast.next
return slow # cycle start
# Find middle of linked list
def find_middle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
Pattern 2: Dummy Head Node
A dummy (sentinel) node before the actual head simplifies edge cases — you never need special handling for insertions/deletions at the head.
# Remove Nth node from end of list
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
# Advance fast n+1 steps
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next # remove the node
return dummy.next
# Merge two sorted lists
def merge_two_lists(l1, l2):
dummy = ListNode()
curr = dummy
while l1 and 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 or l2
return dummy.next
Pattern 3: Reverse a Sublist
# Reverse nodes between positions left and right (1-indexed)
def reverse_between(head, left, right):
dummy = ListNode(0, head)
prev = dummy
# Advance to node before position left
for _ in range(left - 1):
prev = prev.next
curr = prev.next
# Reverse (right - left) times
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = prev.next
prev.next = next_node
return dummy.next
LRU Cache Implementation
LRU (Least Recently Used) cache evicts the least recently accessed item when capacity is exceeded. Implementation requires O(1) get and O(1) put — a hash map alone gives O(1) get but O(n) eviction (need to find LRU item); a doubly linked list alone gives O(1) eviction but O(n) get. Combining both: hash map from key to node (O(1) get), doubly linked list maintaining access order (O(1) move-to-front and O(1) evict-from-tail).
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # key -> node
# Sentinel head and tail
self.head = ListNode() # most recently used end
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _insert_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._insert_front(node)
return node.val
return -1
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = ListNode(value)
node.key = key
self.cache[key] = node
self._insert_front(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
Common Linked List Interview Problems
- Reverse Linked List (I and II — full and partial reversal)
- Linked List Cycle (detection and finding cycle start)
- Merge Two Sorted Lists / Merge K Sorted Lists
- Remove Nth Node From End of List
- Reorder List (1->2->3->4->5 becomes 1->5->2->4->3)
- Palindrome Linked List (find middle, reverse second half, compare)
- LRU Cache (hash map + doubly linked list)
- Add Two Numbers (add digit by digit, carry)
Interview Approach
- Draw the pointers: linked list bugs are almost always pointer errors — visualize before coding
- Dummy head: use it for any problem that might insert or delete at the head
- Two pointers: cycle detection (fast/slow), Nth from end (gap of N), middle (2x speed)
- After reversal: double-check that the new tail points to null, not to a cycle
- Test edge cases: empty list, single node, two nodes, all same values
Frequently Asked Questions
How does Floyd cycle detection algorithm work?
Floyd cycle detection (also called the tortoise and hare algorithm) uses two pointers that move at different speeds through the linked list. The slow pointer advances one node per step; the fast pointer advances two nodes per step. If there is a cycle, the fast pointer will eventually lap the slow pointer — they meet inside the cycle. If there is no cycle, the fast pointer reaches the end (null) first. To find the cycle start node: after the two pointers meet, reset one pointer to the head and leave the other where they met. Advance both at the same speed (one step each). They meet again at the cycle start node. This works because the distance from head to cycle start equals the distance from the meeting point to cycle start, modulo cycle length — a mathematical property of the algorithm.
How do you implement an LRU cache in a coding interview?
An LRU cache requires O(1) get and O(1) put. A hash map alone gives O(1) get but O(n) eviction (must find the LRU item). A doubly linked list alone gives O(1) eviction and O(1) move-to-front, but O(n) lookup. Combining both achieves O(1) for all operations: the hash map stores key-to-node pointers for O(1) access; the doubly linked list maintains access order from most recently used (head) to least recently used (tail). On get: look up node in hash map, move it to front (O(1) pointer changes), return value. On put: if key exists, remove it; create new node, insert at front, add to hash map; if over capacity, remove the tail node and delete from hash map. Use sentinel head and tail nodes to avoid edge cases in pointer manipulation. This is one of the most common senior coding interview questions.
What is the fast and slow pointer technique and when do you use it?
The fast and slow pointer technique uses two pointers traversing the linked list at different speeds. The slow pointer moves one step at a time; the fast pointer moves two steps. This technique solves three categories of problems: (1) Cycle detection: if there is a cycle, the fast pointer laps the slow pointer and they meet inside the cycle. (2) Finding the middle: when the fast pointer reaches the end, the slow pointer is exactly at the middle. For even-length lists, slow lands at the second of two middle nodes. (3) Finding the kth node from the end: advance the fast pointer k steps ahead, then advance both at the same speed until fast reaches the end — slow is at the kth node from the end. The technique is powerful because it solves these problems in O(n) time with O(1) space — no extra data structures needed.
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “How does Floyd cycle detection algorithm work?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Floyd cycle detection (also called the tortoise and hare algorithm) uses two pointers that move at different speeds through the linked list. The slow pointer advances one node per step; the fast pointer advances two nodes per step. If there is a cycle, the fast pointer will eventually lap the slow pointer — they meet inside the cycle. If there is no cycle, the fast pointer reaches the end (null) first. To find the cycle start node: after the two pointers meet, reset one pointer to the head and leave the other where they met. Advance both at the same speed (one step each). They meet again at the cycle start node. This works because the distance from head to cycle start equals the distance from the meeting point to cycle start, modulo cycle length — a mathematical property of the algorithm.” } }, { “@type”: “Question”, “name”: “How do you implement an LRU cache in a coding interview?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “An LRU cache requires O(1) get and O(1) put. A hash map alone gives O(1) get but O(n) eviction (must find the LRU item). A doubly linked list alone gives O(1) eviction and O(1) move-to-front, but O(n) lookup. Combining both achieves O(1) for all operations: the hash map stores key-to-node pointers for O(1) access; the doubly linked list maintains access order from most recently used (head) to least recently used (tail). On get: look up node in hash map, move it to front (O(1) pointer changes), return value. On put: if key exists, remove it; create new node, insert at front, add to hash map; if over capacity, remove the tail node and delete from hash map. Use sentinel head and tail nodes to avoid edge cases in pointer manipulation. This is one of the most common senior coding interview questions.” } }, { “@type”: “Question”, “name”: “What is the fast and slow pointer technique and when do you use it?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “The fast and slow pointer technique uses two pointers traversing the linked list at different speeds. The slow pointer moves one step at a time; the fast pointer moves two steps. This technique solves three categories of problems: (1) Cycle detection: if there is a cycle, the fast pointer laps the slow pointer and they meet inside the cycle. (2) Finding the middle: when the fast pointer reaches the end, the slow pointer is exactly at the middle. For even-length lists, slow lands at the second of two middle nodes. (3) Finding the kth node from the end: advance the fast pointer k steps ahead, then advance both at the same speed until fast reaches the end — slow is at the kth node from the end. The technique is powerful because it solves these problems in O(n) time with O(1) space — no extra data structures needed.” } } ] }