🎓 A1Learner
🔍
0 of 47 lessons completed

Practice: Linked List Problems

Practice with linked list problems is work on problems where each value points to the next value in a chain. It turns the list patterns from earlier lessons into speed and accuracy under time pressure.

Spot a list problem

The input is a chain of nodes, not an indexed list. The question asks about order, a middle, or a reversed chain.

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

head = Node(10, Node(20, Node(30)))
parts = []
current = head
while current is not None:
    parts.append(str(current.value))
    current = current.next
print(" -> ".join(parts))

The reversal template

Most list solutions start with the same walk. Keep a previous pointer, move the current pointer forward, and flip each link as you go.

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

def reverse(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

head = Node(1, Node(2, Node(3, Node(4))))
head = reverse(head)
parts = []
current = head
while current is not None:
    parts.append(str(current.value))
    current = current.next
print(" -> ".join(parts))

Worked problem: find the middle

A slow pointer moves one step and a fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer sits at the middle.

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
slow = head
fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
print("Middle:", slow.value)

Example

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

def merge(a, b):
    dummy = Node(0)
    tail = dummy
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

first = Node(1, Node(3, Node(5)))
second = Node(2, Node(4, Node(6)))
merged = merge(first, second)
parts = []
current = merged
while current is not None:
    parts.append(str(current.value))
    current = current.next
print(" -> ".join(parts))

Key points

  • A linked list is a chain of nodes where each node holds a value and a link to the next node.
  • Use a walk with one moving pointer to visit every node in order.
  • Use two pointers moving at different speeds to find a middle or a cycle.
  • Use a previous pointer to reverse the links in place.

The merge walks both sorted lists at once. It always picks the smaller front value next. The leftover tail is attached in one step, so no value is lost.

Note

a list has no index jump, so reaching the end takes a full walk.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A problem gives a chain of nodes and asks for the middle node in one walk. Which approach fits best?