How do you reverse a linked list?

Reversing a linked list is a common operation in data structures and is often asked in coding interviews. Let’s discuss the iterative method to reverse a linked list first.

Here is the algorithm:

1. Initialize three pointers ‘prev‘ as NULL, ‘curr‘ as head and ‘next‘ as NULL.

2. Iterate through the linked list. In the loop, do following:

- (a) Before changing ‘next‘ of ‘curr‘, store next node using ‘next = curr->next‘

- (b) Now change next of current, set ‘curr->next‘ to ‘prev‘ (this is the actual reversing process)

- (c) Move ‘prev‘ and ‘curr‘ one step forward

3. Return prev (it will become new head).

Assuming ‘ListNode‘ is your data structure for a list node, the code in C++ would be:

ListNode* reverse(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;
    while (curr != NULL) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

This function reverses the linked list by iterating over the list and rearranging the ‘next‘ pointer of each node.

You can also solve this problem using recursion. The idea is to reverse the rest of the list first, then take the first node and attach it to the end of reversed list. The base case is when ‘head‘ is ‘NULL‘.

Here’s the Python recursive solution:

def reverse(self, head):
    if head is None or head.next is None:
        return head
    else:
        newHead = self.reverse(head.next)
        head.next.next = head
        head.next = None
    return newHead

‘head.next.next = head‘ makes the next node of head point to itself, in essence taking the first node and putting it at the end of the reversed list, ‘head.next = None‘ then severs the link between the first node and the rest of the list.

In this code, ‘newHead‘ is the pointer to the new head of the reversed list.