SyntaxPilot
Courses/Python Coding Questions/Lesson 23
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 23 of 30

Linked list questions

build a list with a Node classreverse itfind the middle (slow/fast pointers)detect a cycle

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) uses next as an optional argument.
  • show: start at the head and follow next while the node is not None. The loop checks for None before 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
  1. nxt = node.next: hold the rest;
  2. node.next = prev: turn the coupling;
  3. 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

  1. 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.
  2. How do you reverse a singly linked list? Iterate with prev, node, nxt: save next, point it back, step forward; return prev. O(n) time, O(1) space.
  3. 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.
  4. 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.
  5. Why compare nodes with is? We need the same node object, not equal values.
  6. 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.
  7. 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.
  8. 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's collections.deque is built from blocks linked this way.
  9. Why might the recursive solutions fail in Python? Their depth is the list's length, and Python's recursion limit is about 1,000.
  10. When would you use a linked list in Python? Rarely directly; list and collections.deque usually 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 at None. Build it from the back; walk it with while node: so you never ask None for .value.
  • Reverse: save nxt = node.next, turn node.next = prev, step prev, node = node, nxt; return prev. 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 None never 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 and collections.deque, and the next greater element.