Turning the links round

Reversing a linked list is turning each node's next link back to the node before it. The only hard part is the order: the moment you turn a link you lose the way to the rest of the chain. So before turning it you set the next node aside.

1previous = None
2node = head
3while node is not None:
4    following = node.next
5    node.next = previous
6    previous = node
7    node = following
8return previous

Four lines, always in this order: save the following one, turn the link, move previous on, move node on. When the loop ends node is empty; the head of the reversed list is in previous.

This is a building block of larger solutions. To tell whether a chain is a palindrome without copying it into a list: find the middle with the fast and slow pointers, reverse the second half, then walk the two halves together from their starts, comparing.

Tasks