These are the notes for Python Coding Questions, episode 23: linked list questions. Linked lists are an interview classic, even in Python: build one with a Node class, reverse it without losing anything, find its middle in a single pass, and catch a list that secretly loops back on itself.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real (memory addresses change from run to run).
A quick reminder from episode 20: a class is a blueprint, an object is one thing made from it, an attribute is a value stored on an object (node.value), and __init__ runs when a new object is made.
Q1: A Node class
Real-life example: a train. Each coach carries passengers and is coupled only to the coach behind it. Nobody holds a master list of all coaches: you start at the engine and follow the couplings. The last coach has nothing behind it.
| On the railway | In Python |
|---|---|
| a coach | a node: an object with a value |
| the coupling to the next coach | node.next: a reference to the next node |
| the engine | the head: the first node |
| nothing behind the last coach | None: the end of the list |
A linked list is a chain of nodes joined by next references. Unlike a Python list, the items are not stored side by side with an index; to reach the 100th node you walk 99 links.
Attempt 1: build by hand
class Node:
def __init__(self, value):
self.value = value
self.next = None # the coupling to the next coach
engine = Node("Engine")
engine.next = Node("S1")
engine.next.next = Node("S2")
print(engine)
print(engine.value, engine.next.value, engine.next.next.value)
print(engine.next.next.next.value)
Output:
<__main__.Node object at 0x7f048884ef90>
Engine S1 S2
Traceback (most recent call last):
File "main.py", line 11, in <module>
print(engine.next.next.next.value)
^^^^^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'
print(engine) shows the default text <__main__.Node object at 0x...>. And S2 is the last coach, so S2.next is None, and None has no value: AttributeError: 'NoneType' object has no attribute 'value', the most common linked list error. Writing next.next.next by hand also doesn't scale.
The fix: build from the back, walk until None
- build: go through the values backwards; each new node points at the old head and becomes the new head (adding at the front is O(1)).
Node(v, head)usesnextas an optional argument. - show: start at the head and follow
nextwhile the node is not None. The loop checks forNonebefore ever touching.value.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values): # attach from the back
head = Node(v, head)
return head
def show(head):
parts = []
node = head
while node: # stop at None, the end
parts.append(str(node.value))
node = node.next
return " -> ".join(parts + ["None"])
train = build(["Engine", "S1", "S2", "S3"])
print(show(train))
print(show(build([])))
Output:
Engine -> S1 -> S2 -> S3 -> None
None
Walking a list of n nodes is O(n).
Q2: Reverse a linked list
Real-life example: turning the train around: every coupling has to point backwards. The danger: the moment you unhook coach 1 from coach 2 and point it back, coach 2 is no longer connected to anything you are holding. A careful worker holds the next coach first, then turns the coupling.
Attempt 1: turn the coupling, then follow it
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
parts = []
while head:
parts.append(str(head.value))
head = head.next
return " -> ".join(parts + ["None"])
def reverse(head):
prev, node = None, head
while node:
node.next = prev # turn this coupling around
prev = node
node = node.next # move to the next coach?
return prev
print(show(reverse(build([1, 2, 3, 4]))))
Output:
1 -> None
Three nodes vanished. Why: node.next = prev set node 1's next to None; then node = node.next followed that new None, not node 2. The rest of the list was lost on the very first step.
The fix: three pointers
prev node nxt
None <- 1 -> 2 -> 3 -> 4 -> None
nxt = node.next: hold the rest;node.next = prev: turn the coupling;prev = node; node = nxt: step forward.
When node becomes None, prev is the old last node: the new head. Every node is touched once, O(n) time, and only three variables are used, O(1) extra space.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
parts = []
while head:
parts.append(str(head.value))
head = head.next
return " -> ".join(parts + ["None"])
def reverse(head):
prev, node = None, head
while node:
nxt = node.next # 1. remember the rest
node.next = prev # 2. turn the coupling around
prev = node # 3. step forward
node = nxt
return prev
print(show(reverse(build([1, 2, 3, 4]))))
print(show(reverse(build([7]))), "|", show(reverse(None)))
Output:
4 -> 3 -> 2 -> 1 -> None
7 -> None | None
Always test the empty list and a single node: they are the edge cases interviewers check first.
A recursive version also exists, but its depth equals the length of the list, so it hits RecursionError on long lists (episode 21):
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
parts = []
while head:
parts.append(str(head.value))
head = head.next
return " -> ".join(parts + ["None"])
def reverse_rec(head):
if head is None or head.next is None:
return head # 0 or 1 nodes: already reversed
new_head = reverse_rec(head.next)
head.next.next = head # the next node points back to me
head.next = None
return new_head
print(show(reverse_rec(build([1, 2, 3, 4]))))
Output:
4 -> 3 -> 2 -> 1 -> None
Q3: The middle node and cycle detection
The middle in one pass
Real-life example: Ravi and Asha start at the engine. Ravi walks one coach at a time; Asha walks two at a time. When Asha reaches the end, Ravi has gone exactly half as far: he is at the middle. In code these are the slow and fast pointers (also called the two-pointer technique).
The easy ways (count the nodes and walk again; or copy the values into a Python list, O(n) extra memory) work, but interviewers ask for one pass and O(1) extra space.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def middle(head):
slow = fast = head
while fast.next: # until fast reaches the end
slow = slow.next
fast = fast.next.next
return slow
print(middle(build([1, 2, 3, 4, 5])).value)
print(middle(build([1, 2, 3, 4, 5, 6])).value)
Output:
3
Traceback (most recent call last):
File "main.py", line 20, in <module>
print(middle(build([1, 2, 3, 4, 5, 6])).value)
~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "main.py", line 14, in middle
while fast.next: # until fast reaches the end
^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next'
Five nodes work, six crash. Why: with an even length, fast jumps past the last node straight to None, and the loop then asks None for .next.
Fix: while fast and fast.next:. If fast is None, and stops right there (short-circuit: the right side is not evaluated).
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def middle(head):
slow = fast = head
while fast and fast.next: # fast needs two steps
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
return slow
for vals in [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6], [9]]:
print(vals, "middle:", middle(build(vals)).value)
print(middle(None))
Output:
[1, 2, 3, 4, 5] middle: 3
[1, 2, 3, 4, 5, 6] middle: 4
[9] middle: 9
None
For an even length this returns the second of the two middles (4 for 1..6). For the first middle, use while fast.next and fast.next.next: (with a check for an empty list). About n/2 loop steps: O(n) time, O(1) space.
Detecting a cycle
A cycle means some node's next points back to an earlier node, so the list never ends. Real-life example: runners on a track. On a straight road, the fast runner reaches the end. On a circular track there is no end, and the faster runner always laps the slower one.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
nodes = [Node(v) for v in [1, 2, 3, 4, 5]]
for a, b in zip(nodes, nodes[1:]):
a.next = b
nodes[-1].next = nodes[2] # 5 points back to 3: a loop
node, steps = nodes[0], 0
while node: # "walk until None"
print(node.value, end=" ")
node = node.next
steps += 1
if steps == 20:
print("... still walking")
break
Output:
1 2 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 ... still walking
while node: only stops at None, and a cycle has no None. Without the safety counter, show(), counting the length, everything would hang (and the SyntaxPilot compiler would stop the program after its time limit). Remembering every visited node in a set works, but uses O(n) extra memory:
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def has_cycle_set(head):
seen = set()
while head:
if head in seen: # been here before
return True
seen.add(head) # nodes are hashable by identity
head = head.next
return False
nodes = [Node(v) for v in [1, 2, 3, 4, 5]]
for a, b in zip(nodes, nodes[1:]):
a.next = b
print(has_cycle_set(nodes[0]))
nodes[-1].next = nodes[2]
print(has_cycle_set(nodes[0]))
Output:
False
True
Floyd's cycle detection (tortoise and hare)
- slow moves 1 step, fast moves 2 steps, every turn;
- no cycle: fast reaches
None→False; - cycle: once both are inside the loop, fast gains exactly one node on slow each turn, so the gap shrinks by one until they land on the same node →
True; - compare with
is(the very same object), not==: two different nodes can hold equal values.
They meet before slow finishes one lap of the loop, so the time is O(n), with O(1) space.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow is fast: # the same node: lapped
return True
return False # fast fell off the end
nodes = [Node(v) for v in [1, 2, 3, 4, 5]]
for a, b in zip(nodes, nodes[1:]):
a.next = b
print(has_cycle(nodes[0]))
nodes[-1].next = nodes[2] # make the loop
print(has_cycle(nodes[0]))
print(has_cycle(None), has_cycle(Node(1)))
Output:
False
True
False False
Bonus: where does the cycle start? After they meet, move one pointer back to the head and step both one at a time; they meet again exactly at the first node of the cycle.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = head # restart one pointer
while slow is not fast:
slow, fast = slow.next, fast.next
return slow
return None
nodes = [Node(v) for v in [1, 2, 3, 4, 5]]
for a, b in zip(nodes, nodes[1:]):
a.next = b
nodes[-1].next = nodes[2]
print(cycle_start(nodes[0]).value)
Output:
3
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
node.next.value at the last node |
AttributeError: 'NoneType' object has no attribute 'value' |
the last next is None |
while node: / check for None |
print(node) |
<__main__.Node object at 0x...> |
no __repr__ |
a show() helper or __repr__ |
| building by appending at the end each time | O(n²) to build | walking to the tail every time | build from the back, or keep a tail pointer |
node.next = prev then node = node.next |
1 -> None |
the rest was lost | save nxt first |
returning head after reversing |
only the old first node | the new head is prev |
return prev |
while fast.next: |
AttributeError: 'NoneType' object has no attribute 'next' |
fast became None |
while fast and fast.next: |
| walking a list with a cycle | the program never ends | a cycle has no None |
Floyd's slow/fast check |
slow == fast with an __eq__ on values |
false "cycles" | == compares values |
slow is fast |
| recursive reverse of a long list | RecursionError |
depth = length | the iterative version |
Your turn: the k-th node from the end (solution)
Question: kth_from_end(head, k): the value k nodes from the end, in one pass with O(1) space. For 1..5 and k = 2 the answer is 4.
Idea: give fast a head start of k nodes, then move both one step at a time. When fast reaches None, slow is k nodes behind it: the k-th from the end. If the list has fewer than k nodes, return None.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def kth_from_end(head, k):
fast = head
for _ in range(k): # head start of k nodes
if fast is None:
return None # fewer than k nodes
fast = fast.next
slow = head
while fast:
slow, fast = slow.next, fast.next
return slow.value
lst = build([1, 2, 3, 4, 5])
print(kth_from_end(lst, 2), kth_from_end(lst, 1), kth_from_end(lst, 5))
print(kth_from_end(lst, 6), kth_from_end(None, 1))
Output:
4 5 1
None None
Mini project: a train coach manager
A small Train class keeps a head and a tail, so adding a coach at the end is O(1). It supports len(), print(), in, and turning the train around.
class Coach:
def __init__(self, name):
self.name = name
self.next = None
class Train:
def __init__(self):
self.head = self.tail = None
self._size = 0
def attach(self, name): # add at the end in O(1)
coach = Coach(name)
if self.tail is None:
self.head = self.tail = coach
else:
self.tail.next = coach
self.tail = coach
self._size += 1
def __len__(self):
return self._size
def __iter__(self): # lets for-loops and `in` work
node = self.head
while node:
yield node.name
node = node.next
def __repr__(self):
return "Train(" + " -> ".join(self) + ")"
def turn_around(self):
prev, node = None, self.head
self.tail = self.head
while node:
nxt = node.next
node.next = prev
prev, node = node, nxt
self.head = prev
t = Train()
for name in ["Engine", "S1", "S2", "B1", "Guard"]:
t.attach(name)
print(t, len(t))
print("B1" in t, "A1" in t)
t.turn_around()
print(t)
t.attach("Extra")
print(t)
Output:
Train(Engine -> S1 -> S2 -> B1 -> Guard) 5
True False
Train(Guard -> B1 -> S2 -> S1 -> Engine)
Train(Guard -> B1 -> S2 -> S1 -> Engine -> Extra)
__iter__ is a generator (episode 19): yield hands out one coach name at a time.
Practice questions (with solutions)
1. Merge two sorted linked lists into one sorted list, reusing the nodes.
Solution
A dummy node in front avoids special cases for the first node. Attach the smaller front node each time, then whatever is left. O(n + m) time, O(1) extra space.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
parts = []
while head:
parts.append(str(head.value))
head = head.next
return " -> ".join(parts + ["None"])
def merge(a, b):
dummy = tail = Node(None)
while a and b:
if a.value <= b.value:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b # the rest of whichever is left
return dummy.next
print(show(merge(build([1, 4, 9]), build([2, 3, 10, 12]))))
print(show(merge(None, build([5]))))
Output:
1 -> 2 -> 3 -> 4 -> 9 -> 10 -> 12 -> None
5 -> None
2. Is a linked list a palindrome? (reads the same both ways)
Solution
Find the middle (slow/fast), reverse the second half, and compare it with the first half. O(n) time, O(1) extra space. (Simpler, with O(n) space: copy the values into a list and compare with its reverse.)
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
def is_palindrome(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second = reverse(slow)
while second:
if head.value != second.value:
return False
head, second = head.next, second.next
return True
print([is_palindrome(build(v)) for v in [[1, 2, 2, 1], [1, 2, 3, 2, 1], [1, 2], [], [7]]])
Output:
[True, True, False, True, True]
Note head.next, prev, head = prev, head, head.next: the right side is computed first, so nothing is lost.
3. Remove duplicates from a sorted linked list.
Solution
Equal values sit next to each other, so skip a next node with the same value.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
parts = []
while head:
parts.append(str(head.value))
head = head.next
return " -> ".join(parts + ["None"])
def dedupe(head):
node = head
while node and node.next:
if node.next.value == node.value:
node.next = node.next.next # unlink the duplicate
else:
node = node.next
return head
print(show(dedupe(build([1, 1, 2, 3, 3, 3, 4]))))
print(show(dedupe(build([]))))
Output:
1 -> 2 -> 3 -> 4 -> None
None
4. Length of a linked list, iteratively and recursively.
Solution
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def length(head):
n = 0
while head:
n, head = n + 1, head.next
return n
def length_rec(head):
return 0 if head is None else 1 + length_rec(head.next)
lst = build(list(range(10)))
print(length(lst), length_rec(lst), length(None))
print(length(build(list(range(100_000)))))
Output:
10 10 0
100000
The recursive one would hit RecursionError for the 100,000-node list; the loop has no limit.
Quick quiz
What does this print?
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
head = Node(1, Node(2, Node(3)))
head = head.next
head.next.next = Node(4)
print(head.value, head.next.value,
head.next.next.value)
(A) 1 2 3 (B) 2 3 4 (C) 1 3 4 (D) AttributeError
Answer
(B). head moves to node 2. head.next is node 3, and node 3's next becomes the new node 4. Node 1 still exists, but nothing points to it any more (Python's garbage collector frees it).
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
head = Node(1, Node(2, Node(3)))
head = head.next
head.next.next = Node(4)
print(head.value, head.next.value,
head.next.next.value)
Output:
2 3 4
Interview questions
- Linked list vs Python list? A Python list stores references side by side: O(1) indexing, O(n) insert at the front. A linked list: O(1) insert/remove at the front (or anywhere you already hold a node), O(n) to reach the k-th item.
- How do you reverse a singly linked list? Iterate with
prev,node,nxt: savenext, point it back, step forward; returnprev. O(n) time, O(1) space. - Find the middle in one pass? Slow moves 1, fast moves 2; when fast reaches the end, slow is at the middle. Use
while fast and fast.next. - How does Floyd's cycle detection work? Slow and fast pointers; if there is a cycle fast gains one node per step inside it and they must meet; if not, fast reaches
None. - Why compare nodes with
is? We need the same node object, not equal values. - How do you find where the cycle starts? After the meeting, reset one pointer to the head and move both one step at a time; they meet at the cycle's start.
- What is a dummy (sentinel) node? An extra node before the head so code that attaches nodes doesn't need a special case for the first one.
- What is a doubly linked list? Each node also has
prev, so you can walk both ways and remove a node in O(1). Python'scollections.dequeis built from blocks linked this way. - Why might the recursive solutions fail in Python? Their depth is the list's length, and Python's recursion limit is about 1,000.
- When would you use a linked list in Python? Rarely directly;
listandcollections.dequeusually win. But the ideas (pointers, slow/fast, dummy nodes) appear in many problems, and LRU caches use a linked list with a dict.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Linked list | A chain of nodes joined by next references |
1 -> 2 -> 3 -> None |
| Node | One item: a value and a link | Node(5) |
next |
The reference to the following node | node.next |
| Reference | A name pointing at an object (not a copy) | prev = node |
| Head | The first node | head = build([...]) |
| Tail | The last node | self.tail |
None |
Python's "nothing"; ends the list | node.next is None |
NoneType |
The type of None |
'NoneType' object has no attribute |
AttributeError |
Asking an object for an attribute it doesn't have | None.value |
| Traverse (walk) | Visit every node by following next |
while node: node = node.next |
| Singly linked list | Each node links only forward | today's lists |
| Doubly linked list | Nodes link forward and backward | prev and next |
| Reverse in place | Re-point the existing nodes, no new ones | node.next = prev |
| Pointer | A variable holding a node, moved through the list | prev, node, nxt |
| Two pointers | Two variables moving through data together | slow and fast |
| Slow / fast pointer | Moves 1 / 2 nodes per step | middle, cycle check |
| Short-circuit | and / or skip the right side when the left decides |
fast and fast.next |
| Cycle | A node's next points back to an earlier node |
5 → 3 |
| Floyd's algorithm | Cycle detection with slow and fast pointers | tortoise and hare |
Identity (is) |
The very same object | slow is fast |
| Dummy (sentinel) node | A placeholder node before the head | dummy = Node(None) |
| Palindrome | Reads the same both ways | 1 2 2 1 |
| Garbage collection | Python frees objects nothing refers to | the old node 1 |
__iter__ |
Makes an object loopable | for name in train |
Summary
- A linked list is nodes joined by
next, ending atNone. Build it from the back; walk it withwhile node:so you never askNonefor.value. - Reverse: save
nxt = node.next, turnnode.next = prev, stepprev, node = node, nxt; returnprev. O(n) time, O(1) space. Test empty and one-node lists. - Middle: slow 1 step, fast 2 steps,
while fast and fast.next; the second middle for even lengths. - Cycle: walking until
Nonenever ends. Floyd: slow and fast meet (slow is fast) only if there is a cycle. O(n) time, O(1) space. Reset one pointer to the head to find where the cycle starts. - Next episode: stack and queue questions: a min stack, a queue with two stacks, why
list.pop(0)is slow andcollections.deque, and the next greater element.