How do you reverse a singly linked list in place?
You walk down the list and you flip every link as you go, so that each node points back at the one you came from.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def reverse(head):
previous = None
current = head
while current is not None:
following = current.next
current.next = previous
previous = current
current = following
return previous
So how does it work? You keep three pointers. The previous one points at the node that you have already turned round. The current one is the node you are looking at. And the following one holds the link to the node after it, which you need to keep before you overwrite it.
And the order of the four lines inside the loop is what makes it work. You save the next node first, because you are about to overwrite that link. Then you point the current node back at the previous one, which is the flip. Then you move the previous pointer onto the current node, so it becomes the new tail. And then you move the current pointer on to the node you saved.
the list 1 -> 2 -> 3 -> None
after the flip None <- 1 <- 2 <- 3
the new head is 3
And there is one detail that is worth knowing about. The function gives back the new head, and the new head is the node that was last. It is not the node you started with. If you lose that pointer then you have reversed the list and you cannot get to the front of it any more.
And the complexity is O of n for the time, because you go through the list once, and O of 1 for the space, because you only use three pointers and you build no new nodes.
So the rule to remember is this. Save the next link, flip the current one, and move both pointers on.
The next two questions in this topic show the recursive version and the harder case of reversing only part of the list.