Reversing

To reverse a linked list, you do not move any values. You turn every next reference round, so that it points to the node before. It is the standard practice task for changing references in the right order.

Three names: prev, cur, nxt

Walk along the list once. At each node, point its next back at the node before it. To do this you need three names:

• cur: the node you are working on.
• prev: the node before it, which cur.next should now point to.
• nxt: the node after it. You must save this before you change cur.next, because cur.next is the only reference to the rest of the list.

Step through it, then try the version that forgets to save the next node:

def reverse(head):
    prev, cur = None, head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

Why it is correct

The loop keeps one fact true at the start of every pass:

• At the start: nothing is reversed (prev is None) and everything is still to do (cur is the head). The fact is true.
• Each pass: one node moves from the front of the to-do part to the front of the reversed part. Its next now points to the old prev, which is exactly what the reversed part needs. nxt keeps the to-do part reachable. The fact stays true.
• At the end: cur is None, so the to-do part is empty, and prev is the head of the whole reversed list. Return it.

Each node is handled once, with a fixed amount of work, so the time is O(n). Only three names are used, whatever the length, so the extra space is O(1). This is called reversing in place.

The recursive version

Reversing also has a short recursive form. Let the recursive call reverse the rest of the list. Then attach the first node at the end:

def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next)   # the rest, reversed
    head.next.next = head           # the old second node now points back at head
    head.next = None
    return new_head

head.next still refers to the old second node, which is now the last node of the reversed rest. So head.next.next = head puts head after it.

Reversing part of a list

A common variation is to reverse only the nodes from position left to position right, leaving the rest in place. It needs two extra references:

• the node just before the part, so it can be pointed at the part’s new first node. A dummy node (lesson 2) makes sure this node exists even when left is 1;
• the part’s old first node. After the reversal it is the part’s last node, and it must point to the node just after the part.

In between, run the same loop as above, but only right - left + 1 times. Draw the four nodes on paper before you code: the one before, the first and last of the part, and the one after.

Now try LINK-P3, Reverse a section, then LINK-P4, Turn each group round, which reverses every group of k nodes.