Changing links without losing the list

Every linked list bug is the same bug: you overwrote the only reference to something.

Key idea

What a node is

A node holds a value and a reference to the next node. The last one points at None. There is no length, no index, and no way to go backward unless the problem gives you a doubly linked list.

That single limitation is the source of every technique in this unit. You cannot look back, so anything you will need later has to be held in a variable before you overwrite the link that leads to it.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18head = build([3, 1, 4])19print(to_list(head), head.val, head.next.val)

The traversal loop

Walking a list is one shape, and while node: is the idiomatic condition because None is falsy. Using while node is not None: is equally correct and a little more explicit.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18node = build([3, 1, 4])19total = 020while node:21    total += node.val22    node = node.next23print(total)

Why it works

Deleting needs the node before

To remove a node you must change the next of the node before it, and you cannot get there from the node itself. So a deletion loop carries two references: the current node and its predecessor.

The invariant to hold: prev is always the node immediately before curr, or None when curr is the head.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def remove_all(head, target):19    while head and head.val == target:20        head = head.next            # the head itself may need removing21 22    prev, curr = None, head23    while curr:24        if curr.val == target:25            prev.next = curr.next   # skip over curr26        else:27            prev = curr             # only advance prev when curr survives28        curr = curr.next29    return head30 31print(to_list(remove_all(build([1, 2, 6, 3, 6]), 6)))32print(to_list(remove_all(build([7, 7]), 7)))

Predict the output· 5 min

Predict the output: losing the tail

This tries to reverse the first two nodes and loses part of the list. Type what it prints.

Python

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def to_list(node):6    out = []7    seen = 08    while node and seen < 10:9        out.append(node.val)10        node = node.next11        seen += 112    return out13 14third = Node(3)15second = Node(2, third)16first = Node(1, second)17 18second.next = first19first.next = None20 21print(to_list(second))

Printed output

Code lab· 25 min

Rewiring drills

Three loops that all carry a predecessor. count_nodes returns the length. remove_at removes the node at a given index, doing nothing if the index is out of range. swap_first_two swaps the first two nodes by relinking, not by swapping values.

solution.py

Tests

print(count_nodes(build([1, 2, 3])), count_nodes(build([])))print(to_list(remove_at(build([1, 2, 3]), 0)), to_list(remove_at(build([1, 2, 3]), 2)))print(to_list(remove_at(build([1, 2, 3]), 9)))print(to_list(swap_first_two(build([1, 2, 3]))), to_list(swap_first_two(build([1]))))

Output

Run tests to see output.

Problem· 20 min

Reverse Linked List

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18head = build([3, 1, 4])19print(to_list(head), head.val, head.next.val)

The traversal loop

Walking a list is one shape, and while node: is the idiomatic condition because None is falsy. Using while node is not None: is equally correct and a little more explicit.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18node = build([3, 1, 4])19total = 020while node:21    total += node.val22    node = node.next23print(total)

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def remove_all(head, target):19 while head and head.val == target:20 head = head.next # the head itself may need removing21 22 prev, curr = None, head23 while curr:24 if curr.val == target:25 prev.next = curr.next # skip over curr26 else:27 prev = curr # only advance prev when curr survives28 curr = curr.next29 return head30 31print(to_list(remove_all(build([1, 2, 6, 3, 6]), 6)))32print(to_list(remove_all(build([7, 7]), 7)))

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def to_list(node):6 out = []7 seen = 08 while node and seen < 10:9 out.append(node.val)10 node = node.next11 seen += 112 return out13 14third = Node(3)15second = Node(2, third)16first = Node(1, second)17 18second.next = first19first.next = None20 21print(to_list(second))

print(count_nodes(build([1, 2, 3])), count_nodes(build([])))print(to_list(remove_at(build([1, 2, 3]), 0)), to_list(remove_at(build([1, 2, 3]), 2)))print(to_list(remove_at(build([1, 2, 3]), 9)))print(to_list(swap_first_two(build([1, 2, 3]))), to_list(swap_first_two(build([1]))))