Reverse Linked List

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next     # save next
        curr.next = prev    # turn the arrow
        prev = curr         # step prev
        curr = nxt          # step curr
    return prev

Reverse Linked List. You're given the head of a singly linked list. Reverse it, so every arrow points the other way, and return the new head.

Take one, two, three, four, five. Each node points to the next, and five points to null. Reversed, it reads five, four, three, two, one, and one points to null.

The easy way: copy every value into an array, then walk the list again, writing them back in reverse. It works, but the array costs extra space, one slot per node.

Better: flip the arrows in place. But if you flip a node's arrow first, the rest of the list is lost. So keep three pointers: previous, current, and next. Save next, flip current back to previous, then move both one step.

In code, previous starts at null and current at the head. While current isn't null, save its next, point it at previous, then previous becomes current, and current becomes next. At the end, previous is the new head.

Let's run it. Current is one: save two, flip one to null, step forward. Current is two: save three, flip two back to one. Then three, four and five each turn around. Current is null, so return five.

Each node is visited once, so the time is O of n, with O of one extra space. There's also a recursive version: reverse the rest, then hook the current node onto its end. It's neat, but the call stack grows n deep.

Save, flip, step. That's Reverse Linked List.