Reverse a Linked List

Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, SAP Labs, Qualcomm

Key takeaway

• One of the popular linked list questions that can be solved using both iteration and recursion. 
• A basic problem to improve understanding of pointer manipulation in a linked list. We can also solve many other coding questions based on this idea.

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

• Iterative approach using three-pointers
• Recursive approach using decrease and conquer

Reversing linked list using iteration: Using three-pointers

Solution idea

One idea for reversing a linked list is: Traverse the linked list using a loop and change the next pointer of each node so that it points to its previous node.

Linked list is a linear data structure where each node only points to its next node. So during this process, we should keep track of previous node using some pointer. Before changing the next pointer of the current node, we also need another pointer to track the next node.

Overall, we can use three-pointers for linked list reversal: One for tracking the current node, one for the previous node, and one for the next node. By the end of the loop, we return the new head reference.

Solution steps

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

2. We iterate through 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 curr node, we store the forw node i.e forw = curr->next.
   • We change the next pointer of curr node and point it to prev i.e curr->next = prev.
   • Now reversal of 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 loop, curr becomes NULL, and prev pointer is at the last node, which is the new head of linked list. So we return prev pointer as the new head reference.

At each step of iteration, partially revered linked list size will grow by one.

Solution pseudocode

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
}

C++ implementation code

struct ListNode
{
    int value;
    ListNode* next;
    ListNode(int data)
    {
        value = data;
        next = nullptr;
    }
};

ListNode* reverseLinkedList(ListNode* head)
{
    if (head == nullptr)
        return nullptr;
    ListNode* curr = head;
    ListNode* prev = nullptr;
    ListNode* forw = nullptr;
    while (curr != nullptr)
    {
        forw = curr->next;
        curr->next = prev;
        prev = curr;
        curr = forw;
    }
    return prev;
}

Python implementation code

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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

class ListNode
{
    int val;
    ListNode next;
    ListNode(int x) 
    {  
        val = x; 
        next = null;
    }
}

public class Solution
{
    public 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 are exploring each node and performing constant number of operations at each iteration. So time complexity = n*O(1) = O(1). We use constant extra space, so space complexity = O(1).

Reversing linked list using recursion: Decrease and conquer approach

Solution idea and steps

The critical question is: How 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. The idea is to divide linked list into two parts: The head node and 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 input parameter. This function will return head pointer of the reversed list of size n - 1 i.e. restListHead = reverseLinkedList (head->next).

After this partial reversal, head node will still point to the last node of the reversed list of size n - 1. In other words, next node of the head will be the last node of the reversed list of size n - 1. For the complete reversal, 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.

Solution pseudocode

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
}

C++ implementation code

struct ListNode
{
    int value;
    ListNode* next;
    ListNode(int data)
    {
        value = data;
        next = nullptr;
    }
};

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

Python implementation code

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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

class ListNode
{
    int val;
    ListNode next;
    ListNode(int x) 
    {  
        val = x; 
        next = null;
    }
}

class Solution 
{
    public 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. (Think!)

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!