Reverse a Linked List

Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, Qualcomm.

Key takeaway: One of the basic linked list questions is to learn pointer manipulation and problem-solving using iteration and recursion. We can find many similar questions related to reversing various parts of the linked list.

Let’s understand the problem

A head pointer of a linked list is given, write a program to reverse the linked list. We need to reverse the list by changing the links between nodes.

Example 1

Input: 1->2->3->4->5->NULL

Output: 5->4->3->2->1->NULL

Example 2

Input: 1->2->NULL

Output: 2->1->NULL

Discussed solution approaches

• Reversing linked list iteratively
• Reversing linked list using recursion

Reversing linked list using iteration

Solution idea

One idea is to traverse the linked list using a loop and change the next pointer of each node so that it points to its previous node. During this process, we need to keep track of the previous node. On the other hand, before changing the next of the current node to the previous node, we also need to save the next node.

So, at each iteration, we partially grow the size of the reversed linked list by 1 and keep updating the nodes using three pointers: one for tracking the current node, one for the previous node, and one for the next node.

Solution steps

1. We initialize three pointers: prev as NULL, curr as the head, and forw as NULL.

2. We iterate through the linked list until curr becomes NULL and keep changing each node's next pointer to its previous node. During this process, we update curr, prev, and forw pointers:

   • Before changing the next pointer of the curr node, we store the forw node, i.e., forw = curr->next.
   • We change the next pointer of the curr node and point it to prev, i.e., curr->next = prev.
   • Now the reversal of the curr node is done. So we move prev and curr pointers one step forward, i.e., prev = curr, curr = forw.
3. Finally, by the end of the loop, curr becomes NULL, and the prev pointer is at the last node, which is the new head of the linked list. So we return the prev pointer as the new head.

C++ implementation code

ListNode* reverseLinkedList(ListNode* head) 
{
    if (head == NULL)
        return NULL;

    ListNode* curr = head;
    ListNode* prev = NULL;
    ListNode* forw = NULL;

    while (curr != NULL) 
    {
        forw = curr->next;
        curr->next = prev;
        prev = curr;
        curr = forw;
    }

    return prev;
}

Python implementation code

def reverseLinkedList(head):
    if head is None:
        return None
    curr = head
    prev = None
    forw = None
    while curr is not None:
        forw = curr.next
        curr.next = prev
        prev = curr
        curr = forw
    return prev

Java implementation code

ListNode reverseLinkedList(ListNode head)
{
    if (head == null)
        return null;
    
    ListNode curr = head;
    ListNode prev = null;
    ListNode forw = null;
    
    while (curr != null) 
    {
        forw = curr.next;
        curr.next = prev;
        prev = curr;
        curr = forw;
    }
        
    return prev;
}

Time and space complexity analysis

We explore each node and perform constant operations at each iteration. So, the time complexity = n*O(1) = O(1). We use constant extra space, so the space complexity is O(1).

Reversing linked list using recursion

Solution idea and steps

The critical question is: Can we solve this problem using recursion? In other words, how can we solve reversing a linked list problem using the solution of its smaller subproblems? Let's think.

Suppose the length of the linked list is n. Now we divide the linked list into two parts: The head node and the remaining linked list of size n - 1 (smaller sub-problem). We recursively reverse the remaining linked list of size n - 1 by calling the same function with head->next as an input parameter. Now this will return the head pointer of the reversed list of size n - 1 i.e. restListHead = reverseLinkedList (head->next).

After this, the head node will still point to the last node of the reversed list of size n - 1. In other words, the next node of the head will be the last node of the reversed list of size n - 1. So for the complete reversal, the head should be the last node. So, we do the following operations to ensure this: head->next->next = head, head->next = NULL.

Base case: if (head == NULL || head->next == NULL), return NULL.

C++ implementation code

ListNode* reverseLinkedList(ListNode* head)
{
    if (head == NULL || head->next == NULL)
        return head;
    
    ListNode* restListHead = reverseLinkedList(head->next);
    head->next->next = head;
    head->next = NULL;
    return restListHead;
}

Python implementation code

def reverseLinkedList(head):
    if head is None or head.next is None:
        return head
    
    restListHead = reverseLinkedList(head.next)
    head.next.next = head
    head.next = None
    return restListHead

Java implementation code

ListNode reverseLinkedList(ListNode head) 
{
    if (head == null || head.next == null)
        return head;
            
    ListNode restListHead = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return restListHead;
}

Time and space complexity analysis

We are recursively solving the problem of size n with a smaller sub-problem of size n - 1. Recurrence relation: T(n) = T(n - 1) + c.

• The height of the recursion tree is O(n) because the input size is decreasing by 1. At each stage of recursion, we are doing constant operations. So time complexity = O(n).
• Space complexity = O(n), for recursion stack space.

Critical ideas to think!

• Can we optimize the 1st approach and solve it using only two pointers?
• How can we reverse a linked list using stack?
• Why space complexity of the recursive solution is O(n)?
• How is the head getting fixed in the recursive method? Why don’t we use head->next = head to fix the head?

Comparison of time and space complexities

• Iterative approach: Time = O(n), Space = O(1).
• Recursive approach: Time = O(n), Space = O(n).

Suggested problems to practice

• Reverse a linked list from position M to N.
• Reverse a linked list in groups of a given size.
• Reverse a linked list using stack.
• Reverse a circular linked list.
• Reverse the first k elements of the given linked list. 
• Reverse a doubly linked list.

Enjoy learning, Enjoy algorithms!