How would you reverse a linked list?

Reversing a linked list involves changing the direction of next pointers in a linked list. This means if you have a linked list A -> B -> C -> D -> NULL, it should be turned into NULL <- A <- B <- C <- D.

Here is a simple algorithm demonstrating this often-solved problem:

Assume we have a class defining nodes:

class Node:
    def __init__(self, x):
        self.value = x
        self.next = None

We can solve the problem using iteration:

def reverseList(self, head):
    previous, current = None, head
    while current:
        next_node, current.next = current.next, previous
        previous, current = current, next_node
    return previous

Here, we:

1. Maintain two pointers: ‘previous‘ initialized as ‘None‘ and ‘current‘ initialized as ‘head‘.

2. In every iteration, we update the ‘next‘ pointer of the ‘current‘ node to point to the ‘previous‘ node.

3. Finally, we return the new ‘head‘ of the linked list, which is the ‘previous‘ pointer.

Now, let’s break it down how the above iterative solution works:

Imagine initially

A->B->C->D->None

Let’s take ‘previous = None‘ and ‘current = head‘ (A).

In the loop, we keep a reference to ‘current.next‘ (B), then change ‘current.next‘ to ‘previous‘ (None), finally move ‘previous‘ and ‘current‘ one step forward.

Now it becomes

None<-A  B->C->D->None
     previous current

Do the same steps again:

None<-A<-B  C->D->None
        previous current

And it ends like this:

None<-A<-B<-C<-D
             previous(current)        

When ‘current‘ becomes ‘None‘, it means we reached the tail of the original linked list (the new head of the reversed one). The algorithm returns ‘previous‘, which points to the head of the reversed list.

We don’t have to worry about losing the links between nodes. For example, when switching B and C, because before we change ‘current.next‘, we’ve already saved the reference to it in ‘next_node‘.

As for the time complexity, this algorithm performs with O(n), where n represents the length of the linked list. This is because every node in the list is traversed exactly once.

Finally, please note that, although in-place reversal like this is common and neat, it’s destructive – it destroys the original list by changing the node in place. If you need to keep the original list unchanged, you will need to clone the nodes.