Linked List
Pointer-based list — traversal, reversal, and the fast/slow pointer technique
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
A is a chain of nodes. Each node stores a value and a pointer to the next node. Unlike an array, elements are scattered in memory — there's no index lookup.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build 1 → 2 → 3
head = ListNode(1, ListNode(2, ListNode(3)))Traversal — always use a pointer, never mutate the original:
python def traverse(head): curr = head while curr: print(curr.val) curr = curr.next # move pointer forward
Complexity vs arrays:
| Operation | Array | Linked List | |---|---|---| | Access by index | O(1) | O(n) — must traverse | | Insert at front | O(n) — shift | O(1) — update pointer | | Insert at back | O(1) amortized | O(n) — or O(1) with tail ptr | | Search by value | O(n) | O(n) |
Reverse a linked list — the most common interview operation:
python def reverse(head): prev = None curr = head while curr: next_node = curr.next # save next curr.next = prev # reverse the pointer prev = curr # advance prev curr = next_node # advance curr return prev # prev is now the new head # 1→2→3→None becomes 3→2→1→None
Fast/slow pointers — the key two-pointer technique for linked lists:
python def find_middle(head): """Slow moves 1 step, fast moves 2 — when fast reaches end, slow is at middle.""" slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow # middle node def has_cycle(head): """If fast catches up to slow, there's a cycle (Floyd's algorithm).""" slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
Dummy node trick — simplifies edge cases when the head might change: ``python def remove_nth_from_end(head, n): dummy = ListNode(0, head) # dummy points to head fast = slow = dummy for _ in range(n + 1): fast = fast.next # advance fast n+1 steps while fast: slow = slow.next fast = fast.next # move both until fast reaches end slow.next = slow.next.next # skip the target node return dummy.next # dummy.next handles head-removal case
Examples
Merge two sorted linked lists
Dummy node eliminates the special case of "which list provides the first node"
def merge_two_lists(l1, l2):
dummy = ListNode(0)
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 # attach remaining nodes
return dummy.next
# 1→3→5 + 2→4→6 → 1→2→3→4→5→6Find cycle start with Floyd's algorithm
Phase 1 detects the cycle; Phase 2 exploits mathematical symmetry to find the entry point
def detect_cycle(head):
"""Find the node where a cycle begins, or None."""
slow = fast = head
# Phase 1: detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # no cycle
# Phase 2: find cycle start
slow = head # reset slow to head
while slow != fast:
slow = slow.next
fast = fast.next # both move 1 step now
return slow # meeting point is cycle startHow well did you understand this?
Practice Problems
Next in Algorithms & Data Structures
Two Pointers