Traversing and building lists

Two patterns power nearly every problem in this section. Get them into your fingers now.

Traversal

Walk from the head, following Next, until you fall off the end (nil):

node = head
while node exists:
    // use node.value
    node = node.next

That loop visits every node exactly once — O(n). Summing, counting, searching, and collecting values are all just this loop with a different body.

Building a list with a dummy head

Constructing a list forwards is awkward, since the head doesn't exist until you make the first node. The fix is a throwaway dummy node: build off its Next, then return dummy.Next at the end.

dummy = new ListNode()
tail = dummy
for each v in values:
    tail.next = new ListNode(v)
    tail = tail.next
return dummy.next   // the real head

The dummy means you never have to special-case "is this the first node?" — tail always points at the last node built, so you just keep appending.

Rewiring

To splice a node out, point its predecessor past it:

prev.next = prev.next.next   // drop the node after prev

To splice one in:

newNode.next = prev.next
prev.next = newNode

Order matters: set the new node's Next before you overwrite prev.Next, or you'll lose the rest of the list. With traversal, the dummy-head builder, and these two rewires, you can solve everything that follows.