Linked lists: formulas, shortcuts & solved examples
What it is
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 contiguous, so inserting or deleting at a known position is cheap, but reaching the k-th element requires walking from the head. Interviewers like linked lists because pointer manipulation exposes careless thinking quickly.
Key rules
Types
- Singly linked: each node points to the next; the last points to NULL.
- Doubly linked: each node also points to the previous node, allowing O(1) deletion when you hold the node.
- Circular: the last node points back to the head.
Operation costs (singly linked, n nodes)
| Operation | Cost |
|---|---|
| Insert at head | O(1) |
| Insert at tail | O(n), or O(1) with a tail pointer |
| Access k-th node | O(k) |
| Search | O(n) |
| Delete after a known node | O(1) |
| Delete a given value | O(n) |
Node in Python
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
Standard techniques
- Dummy (sentinel) head: simplifies edge cases when the real head may change.
- Slow and fast pointers: slow moves one step, fast moves two. Used for the middle node and cycle detection (Floyd's algorithm).
- Gap of k: move one pointer k steps ahead, then move both together; when the leader hits the end, the follower is k from the end.
- Three-pointer reversal: prev, curr, next.
Shortcuts
- Middle node. When fast reaches the end, slow is at the middle. For an even count this standard loop lands on the second of the two middle nodes.
- Cycle check. If slow and fast ever meet, there is a cycle; if fast hits NULL, there is none. O(n) time, O(1) space.
- Draw three boxes. Before coding any pointer change, sketch three nodes and redraw arrows step by step. Most bugs come from overwriting
nextbefore saving it.
Solved examples
Example 1: Reverse a list
prev, curr = None, head # head: 10 -> 20 -> 30 -> 40 -> 50
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
head = prev
Solution. Each iteration flips one arrow. After five iterations, prev points to 50 and the list reads 50 -> 40 -> 30 -> 20 -> 10. Time O(n), space O(1).
Example 2: Find the middle
List: 1 -> 2 -> 3 -> 4 -> 5 -> 6.
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
print(slow.val)
Solution. Positions (slow, fast): start (1, 1), then (2, 3), (3, 5), (4, NULL past 6). The loop stops since fast is NULL. Output 4, the second middle of an even-length list. For 1 to 5 it would print 3.
Example 3: Remove the 2nd node from the end
List: 7 -> 14 -> 21 -> 28 -> 35, remove the 2nd from the end (28).
dummy = Node(0, head)
lead = lag = dummy
for _ in range(2 + 1):
lead = lead.next
while lead:
lead = lead.next
lag = lag.next
lag.next = lag.next.next
head = dummy.next
Solution. Lead starts 3 steps ahead (at 21). Both move until lead passes 35; lag is then at 21, just before 28. Skipping it gives 7 -> 14 -> 21 -> 35. The dummy node means removing the head itself (k = 5) needs no special case.
Example 4: Merge two sorted lists
Lists: 1 -> 4 -> 9 and 2 -> 3 -> 10 -> 12.
def merge(a, b):
dummy = tail = Node(0)
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
Solution. Compare heads repeatedly: 1, 2, 3, 4, 9, then list a is empty, so the remainder 10 -> 12 is attached directly. Result 1 -> 2 -> 3 -> 4 -> 9 -> 10 -> 12, in O(m + n) time and O(1) extra space. This is the merge step of merge sort on linked lists.
Common mistakes
- Losing the rest of the list. Changing
curr.nextbefore saving it in a temporary variable disconnects everything after curr. - Not handling an empty list or a single node. Always test head = None and a one-node list.
- Dereferencing NULL in the fast pointer loop. The condition must check both
fastandfast.next. - Forgetting to update the head. After reversal or deleting the first node, return the new head; the old variable still points to the old first node.
- Assuming linked lists beat arrays for everything. They have poor cache locality and O(n) indexing; arrays usually win unless you insert and delete in the middle often.
Practice now: https://www.testsworld.com/mocks