Linked Lists
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.
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.
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.
Gotcha
Advance `prev` only when the node survives
The most common bug here is advancing prev on every pass. When a node is removed, prev must stay where it is, because the node before the removed one is now the predecessor of whatever comes next.
Advancing it anyway leaves prev pointing at a node that is no longer in the list, so a second consecutive removal writes into a detached node and silently does nothing. That is why the test above ends with two 6s that are not adjacent and a case where both nodes are removed.
Edge cases
The head is always the special case
There is no node before the head, so removing it cannot be done through a predecessor. The loop above handles that with a separate while before the main pass.
That separate loop is easy to forget and easy to get wrong: it has to be a while, not an if, because several nodes at the front might all need removing. The next lesson shows the trick that makes this special case disappear entirely.
Why it works
Reversing a link needs three references
To make a node point backward you must first save where it was pointing, or you lose the rest of the list. That is three references at once: the node behind, the current node, and the one ahead.
Write the save first, before any assignment that would destroy it. Every reversal-style loop in this unit is that same ordering discipline, and getting the order wrong is the single most common way to produce a list that loops forever.
Predict the output: losing the tail
This tries to reverse the first two nodes and loses part of the list. Type what it prints.
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.
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 the tests when you are ready.
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.