Singly Linked List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return f"ListNode({self.val})"
def make_list(values):
"""Create linked list from Python list"""
dummy = ListNode(0)
curr = dummy
for v in values:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def list_to_array(head):
"""Convert linked list to Python list"""
result = []
while head:
result.append(head.val)
head = head.next
return result
Core Operations
Traversal — O(n)
def traverse(head):
curr = head
while curr:
print(curr.val, end=" -> ")
curr = curr.next
print("None")
Insert at Head — O(1)
def prepend(head, val):
new_node = ListNode(val)
new_node.next = head
return new_node # new head
Insert at Tail — O(n)
def append(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
Delete by Value — O(n)
def delete(head, val):
dummy = ListNode(0, head)
curr = dummy
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return dummy.next
Classic Problems
Reverse a Linked List
def reverse(head):
"""Iterative — O(n) time, O(1) space"""
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev # new head
def reverse_recursive(head, prev=None):
"""Recursive — O(n) time, O(n) space"""
if not head:
return prev
next_node = head.next
head.next = prev
return reverse_recursive(next_node, head)
# Test
head = make_list([1, 2, 3, 4, 5])
reversed_head = reverse(head)
print(list_to_array(reversed_head)) # [5, 4, 3, 2, 1]
Detect a Cycle (Floyd's Algorithm)
def has_cycle(head):
"""Slow and fast pointer — O(n) time, O(1) space"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def find_cycle_start(head):
"""Find where the cycle begins"""
slow = fast = head
# Phase 1: detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry point
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle start
Find Middle Node
def find_middle(head):
"""Fast & slow pointer"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# [1,2,3,4,5] → 3 (index 2)
# [1,2,3,4] → 3 (second middle)
Merge Two Sorted Lists
def merge_sorted(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
return dummy.next
# Test
a = make_list([1, 3, 5, 7])
b = make_list([2, 4, 6])
merged = merge_sorted(a, b)
print(list_to_array(merged)) # [1, 2, 3, 4, 5, 6, 7]
Remove Nth Node from End
def remove_nth_from_end(head, n):
"""Two-pointer — O(n) single pass"""
dummy = ListNode(0, head)
ahead = behind = dummy
# Move 'ahead' n+1 steps ahead
for _ in range(n + 1):
ahead = ahead.next
# Move both until 'ahead' reaches end
while ahead:
ahead = ahead.next
behind = behind.next
# Remove the target node
behind.next = behind.next.next
return dummy.next
Merge K Sorted Lists
import heapq
def merge_k_sorted(lists):
"""Use a min-heap — O(N log K) where N=total nodes, K=lists"""
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
curr = dummy
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Doubly Linked List
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = self.tail = None
self.size = 0
def append(self, val):
node = DLNode(val)
if not self.tail:
self.head = self.tail = node
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
self.size += 1
def prepend(self, val):
node = DLNode(val)
if not self.head:
self.head = self.tail = node
else:
node.next = self.head
self.head.prev = node
self.head = node
self.size += 1
def delete(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
self.size -= 1
def __repr__(self):
items = []
curr = self.head
while curr:
items.append(str(curr.val))
curr = curr.next
return " <-> ".join(items)
LRU Cache with Doubly Linked List + HashMap
from collections import OrderedDict
class LRUCache:
"""Using OrderedDict — simple but interview-worthy"""
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # evicts key 2
print(cache.get(2)) # -1 (evicted)
Exercises
Exercise 1: Palindrome Linked List
Check if a linked list is a palindrome in O(n) time and O(1) space.
Solution:
def is_palindrome(head):
# Step 1: Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse second half
prev = None
curr = slow
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
# Step 3: Compare halves
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
Exercise 2: Reorder List
Given [1,2,3,4,5], reorder to [1,5,2,4,3].
Solution:
def reorder_list(head):
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
second = slow.next
slow.next = None
prev = None
while second:
next_n = second.next
second.next = prev
prev = second
second = next_n
# Merge two halves
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2