Linked list patterns

Linked-list questions test pointer handling under pressure. A few patterns cover nearly all of them. (The Python course's linked-lists lesson builds the Node class used here.)

Reversing in place

Walk the list once, turning each next arrow around. Three variables: prev (the reversed part so far), current, and nxt (saved before the arrow is changed, or the rest of the list is lost).

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

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next       # save the rest of the list
        current.next = prev      # turn the arrow around
        prev = current
        current = nxt
    return prev

head = Node(1, Node(2, Node(3)))
head = reverse(head)
values = []
while head:
    values.append(head.value)
    head = head.next
print(values)

Step through and watch each node's next change in the memory view. O(n) time and O(1) extra space. Draw the three boxes on paper (or the whiteboard) before coding this; everyone does.

Fast and slow pointers

Move slow one node at a time and fast two:

• When fast reaches the end, slow is at the middle.
• If the list has a cycle, fast laps slow and they meet. If not, fast reaches None. This is Floyd's cycle-finding algorithm: O(n) time and O(1) space, where a set of seen nodes would need O(n) space.

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

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

a, b, c, d = Node("a"), Node("b"), Node("c"), Node("d")
a.next, b.next, c.next = b, c, d
print("straight list:", has_cycle(a))
d.next = b                       # d points back to b: a cycle
print("with a cycle:", has_cycle(a))

Then, to find where the cycle starts, put one pointer back at the head and move both one step at a time: they meet at the cycle's first node. (The proof is a nice exercise in counting steps.)

Merging, and the dummy head

Merge two sorted lists into one sorted list. Compare the two fronts and attach the smaller one. A dummy node in front of the result removes the special case "is the result still empty?":

def merge(a, b):
    dummy = tail = Node(0)
    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          # whatever is left
    return dummy.next

The dummy head helps whenever the first node might change: deleting nodes, inserting in sorted order, partitioning.

Mark lesson complete