Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Reversing a Linked List

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Linked List

Introduction

linked list is a data structure that stores the data(information) in a node. Every node in a linked list stores the address of its neighboring node. 

Structure of Linked List

The last node of the linked list points to a NULL address representing the end of the linked list. To traverse the linked list, the address to the first node is stored in a node pointer usually called ‘HEAD’.

Structure of Linked List

The linked list is one such lovely topic that enchants every interviewer with its magic of pointers. If you are preparing for a technical interview, you must take advantage of every opportunity to reveal your feelings for the interviewer's crush (linked list). In this blog, we will look at a well-known interview problem that is close to every interviewer's heart: reverse a linked list.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

Problem Statement

The ‘HEAD’ pointer of a linked list is given. Return the ‘HEAD’ pointer of the reversed linked list.

Input

Enter the number of nodes in the linked list: 4
Enter the data of nodes: 1 2 3 4

Output

Reversed linked list: 4 3 2 1

Explanation

 

illustration image

Recommended: Try the Problem yourself before moving on to the Solution

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Method 1: Stack

Stack follows the LIFO principle, which means the element that comes at the last should be shown first. That’s exactly what we want. We want to print the last node of the linked list first and so on. 

Using stack to create a reversed linked list is pretty simple. Put all the nodes of the linked list in a stack. 

stack

Then, start popping out the nodes from the stack. Set the ‘NEXT’ pointer of the current popped node to the previously popped node.

illustration image

Refer to the algorithm given below for a better understanding.

Also read - Merge sort in linked list

Algorithm

  • If the ‘HEAD’ points to NULL (means linked list is empty), then:
    • Return NULL.
  • Create a stack ‘NODE_STACK’.
  • Set a pointer, ‘CURRENT’ (node pointer to point at the current node during linked list traversal) equal to the ‘HEAD’.
  • While CURRENT -> NEXT is not equal to NULL, do:
    • Push ‘CURRENT’ into the ‘NODE_STACK’.
    • Set ‘CURRENT’ = CURRENT -> NEXT.
  • Set ‘HEAD’ equal to ‘CURRENT’ (‘CURRENT’ after the while loop, points to the last element of the linked list).
  • Initialise ‘PREVIOUS_TOP’ with ‘CURRENT’ node to store the previous top element of the stack.
  • While ‘NODE_STACK’ is not empty, do:
    • Set ‘CURRENT’ equal to the top element of the ‘NODE_STACK’.
    • Pop the top element off ‘NODE_STACK’.
    • Set PREVIOUS_TOP -> NEXT = CURRENT (Set the next pointer of the previous top of the stack equal to the current top).
    • Set ‘PREVIOUS_TOP’ equal to ‘CURRENT’.
  • Set PREVIOUS_TOP -> NEXT equal to NULL. (To represent the end of the linked list).

Program

#include <iostream>
#include <stack>
using namespace std;

// 'NODE' class to store linked list nodes.
class Node
{

public:
    int data;
    Node *next;

    // Constructor to create a node with given data.
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};

// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{

    // 'HEAD' pointer to store the address of the first node.
    Node *head;

public:
    LinkedList()
    {
        head = NULL;
    }

    // Function to print the linked list elements.
    void printLinkedList()
    {

        /* 'CURRENT' node pointer traverses through the linked list.
            Set 'CURRENT' node equal to the first node of the linked list.
        */
        Node *current = head;

        // Loop to traverse the linked list.
        while (current)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    // Function to insert nodes in the linked list.
    void insert(int data)
    {

        /*  If linked list is empty, create a new node
            and direct the 'HEAD' node to the newly created node.
        */
        if (head == NULL)
        {
            head = new Node(data);
            return;
        }

        // Else traverse the linked list until the end of the list is encountered.
        Node *current = head;
        while (current->next)
        {
            current = current->next;
        }

        // Create and insert a new node at the end of the linked list.
        current->next = new Node(data);
    }

    void reverseLinkedList()
    {

        // Declare a stack pointer to store the linked list nodes.
        stack<Node *> nodeStack;

        // Set the 'CURRENT' node equal to the first node of the linked list.
        Node *current = head;

        /*  Traverse through the linked list and
            push the nodes into the stack.
        */
        while (current->next)
        {
            nodeStack.push(current);
            current = current->next;
        }

        // Point 'HEAD' equal to 'CURRENT'
        head = current;

        // Initialise 'PREVIOUS_TOP' with 'CURRENT' node to store the previous top element.
        Node *previousTop = current;
        while (!nodeStack.empty())
        {
            current = nodeStack.top();
            nodeStack.pop();

            // Set the next pointer of the previous top of the stack equal to the current top.
            previousTop->next = current;
            previousTop = current;
        }
        previousTop->next = NULL;

        // Print the reversed linked list.
        printLinkedList();
    }
};

int main()
{
    int totalNodes;
    cout << "Enter the number of nodes in the linked list: ";
    cin >> totalNodes;

    cout << "Enter the data of nodes: ";
    LinkedList *givenList = new LinkedList();
    for (int i = 0; i < totalNodes; i++)
    {
        int data;
        cin >> data;
        givenList->insert(data);
    }
    
    cout << "Reversed linked list: ";
    givenList->reverseLinkedList();
}

 

Input

Enter the number of nodes in the linked list: 6
Enter the data of nodes: 1 2 3 6 5 4

Output

Reversed linked list: 4 5 6 3 2 1

Complexity Analysis

Time Complexity: Traversal through the linked list is required to store the nodes of the linked list in the stack. Similarly, the linked list nodes are popped off the stack one by one until the stack is empty. Both these operations are linear-time operations. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

Space Complexity: Additional space is required to store the nodes of the linked list in the stack. The space required is linearly proportional to the size of the linked list. So, the space complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

 

Method 2: Iteration with constant space

In the previous method, we first traversed through the linked list to store all the nodes. If you notice, we only need two nodes at a time for reversal: ‘PREVIOUS_TOP’ and ‘CURRENT’ to reverse the pointer of one node at a time.

illustration image

Rather than start reversing the linked list from end, we can start the reversal from the Rather than start reversing the linked list from the end, we can start the reversal from the beginning.

illustration image

The problem we’ll face here is that if we redirect the ‘NEXT’ pointer of ‘NODE_2’, the linked list is split into two parts. This makes moving to the ‘NEXT’ node impossible. Refer to the figure given below for the illustration of the same.

illustration image

The solution for this problem is to add a pointer ‘NEXT_TO_CURRENT’ pointer to store the address of the pointer ‘NEXT’ to current.

illustration image

After setting the pointer of the ‘NEXT’ node, we can make the ‘PREVIOUS_TOP’ node our ‘CURRENT ’node and move the ‘CURRENT’ node to the next node. 

illustration image

These actions are repeated until the linked list is completely traversed. In the end, the ‘PREVIOUS_TOP’ points to the last node of the linked list. As the last node of a linked list becomes the first node when the linked list is reversed, we consider ‘PREVIOUS_TOP’ to be the ‘HEAD’ of the newly created linked list. Refer to the algorithm given below for a better understanding.

Algorithm

  • Set the ‘CURRENT’ equal to ‘HEAD’.
  • Set the ‘PREVIOUS_TOP’ equal to NULL(First element of the linked list should point to NULL after reversal).
  • Declare ‘NEXT_TO_CURRENT’ node pointer.
  • While ‘CURRENT’ is not equal to NULL, do:
    • Set NEXT_TO_CURRENT  = CURRENT -> NEXT.
    • Set CURRENT -> NEXT = PREVIOUS_TOP.
    • Set PREVIOUS_TOP = CURRENT.
    • Set CURRENT = NEXT.
  • Set HEAD = PREVIOUS_TOP.

Program

#include <iostream>
using namespace std;
 
// 'NODE' class to store linked list nodes.
class Node
{
 
public:
    int data;
    Node *next;
 
    // Constructor to create a node with given data.
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{
 
    // 'HEAD' node to store the address of the first node.
    Node *head;
 
public:
    LinkedList()
    {
        head = NULL;
    }
 
    // Function to print the linked list elements.
    void printLinkedList()
    {
 
        /* 'CURRENT' node pointer traverses through the linked list.
            Set 'CURRENT' node equal to first node of the linked list.
        */
        Node *current = head;
 
        // Loop to traverse the linked list.
        while (current)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
 
    // Function to insert nodes in the linked list.
    void insert(int data)
    {
 
        /*  If linked list is empty, create a new node
            and direct the 'HEAD' node to the newly created node.
        */
        if (head == NULL)
        {
            head = new Node(data);
            return;
        }
 
        // Else traverse the linked list until end of the list is encountered.
        Node *current = head;
        while (current->next)
        {
            current = current->next;
        }
 
        // Create and insert a new node at the end of the linked list.
        current->next = new Node(data);
    }
 
    void reverseLinkedList()
    {
 
       // Set 'CURRENT' node equal to the first node of the linked list.
        Node *current = head;
 
        // Initialise 'PREVIOUS_TOP' as NULL to store the previous top element.
        Node *previousTop = NULL;
 
        // Traverse through the linked list and redirecting the pointers to the previous elements.
        while (current)
        {
 
            // Initialise 'NEXT_TO_CURRENT' node pointer with CURRENT -> NEXT.
            Node *nextToCurrent = current->next;
 
            // Redirect 'NEXT' pointer of the 'CURRENT' node.
            current->next = previousTop;
 
            // Move pointers to the next node of linked list.
            previousTop = current;
            current = nextToCurrent;
        }
 
        // Point 'HEAD' equal to the last node of the linked list.
        head = previousTop;
 
        // Print the reversed linked list.
        printLinkedList();
    }
};
 
int main()
{
    int totalNodes;
    cout << "Enter the number of nodes in the linked list: ";
    cin >> totalNodes;
 
    cout << "Enter the data of nodes: ";
    LinkedList *givenList = new LinkedList();
    for (int i = 0; i < totalNodes; i++)
    {
        int data;
        cin >> data;
        givenList->insert(data);
    }
    cout << "Reversed linked list: ";
    givenList->reverseLinkedList();
}

Input

Enter the number of nodes in the linked list: 5
Enter the data of nodes: 10 32 20 11 2

Output

Reversed linked list: 2 11 20 32 10

Complexity Analysis

Time Complexity: Traversal through the linked list is required to reverse the pointers of the linked list nodes. Traversal through the linked list is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

Space Complexity: Constant space is required to store the ‘PREVIOUS_TOP’, ‘CURRENT’, and ‘NEXT_TO_CURRENT’ pointers. So, the space complexity of the method is O(1).

Must Read  C Program to Reverse a Number

Method 3: Recursion with constant space

The operations discussed above can also be achieved using recursion. The ‘PREVIOUS_TOP’, ‘CURRENT’, and ‘HEAD’ pointers are fed to the recursive functions as the function parameters.

The base function of the recursive function is to check whether the ‘NEXT’ pointer to the ‘CURRENT’ node exists. If no ‘NEXT’ pointer exists, that means we have encountered the last node of the list. So, the last node of the linked list should be stored as the head of the reversed linked list.

Like the iterative solution, we set the ‘NEXT’ node of the ‘CURRENT’ node into a variable ‘NEXT_TO_CURRENT’. The ‘NEXT’ pointer of the ‘CURRENT’ node is redirected to the ‘PREVIOUS_TOP’. After redirection, ’PREVIOUS_TOP’ is set to ‘CURRENT’, and the ‘CURRENT’ is set to ‘NEXT_TO_CURRENT’. The recursive function will be called using the new parameters. Refer to the given algorithm for a better understanding.

Algorithm

  • If CURRENT -> NEXT is equal to NULL, then:
    • Set ‘HEAD’ = ‘CURRENT’.
    • Set CURRENT -> NEXT = PREVIOUS_TOP.
    • Return
  • Set NEXT_TO_CURRENT = CURRENT -> NEXT.
  • Set CURRENT -> NEXT = PREVIOUS_TOP.
  • Call the recursive function with ‘NEXT_TO_CURRENT’ and ‘CURRENT parameters.

Program

#include <iostream>
using namespace std;
 
// 'NODE' class to store linked list nodes.
class Node
{
 
public:
    int data;
    Node *next;
 
    // Constructor to create a node with given data.
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{
 
    // 'HEAD' node to store the address of the first node.
    Node *head;
 
public:
    LinkedList()
    {
        head = NULL;
    }
 
    // Function to print the linked list elements.
    void printLinkedList()
    {
 
        /* 'CURRENT' node pointer traverses through the linked list.
            Set 'CURRENT' node equal to first node of the linked list.
        */
        Node *current = head;
 
        // Loop to traverse the linked list.
        while (current)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
 
    // Function to insert nodes in the linked list.
    void insert(int data)
    {
 
        /*  If linked list is empty, create a new node
            and direct the 'HEAD' node to the newly created node.
        */
        if (head == NULL)
        {
            head = new Node(data);
            return;
        }
 
        // Else traverse the linked list until end of the list is encountered.
        Node *current = head;
        while (current->next)
        {
            current = current->next;
        }
 
        // Create and insert a new node at the end of the linked list.
        current->next = new Node(data);
    }
 
    void reverseLinkedListHelper(Node *current, Node *previousTop)
    {
 
        /*  Last node of the linked list.
        Point 'HEAD' to this node.
    */
        if (!current->next)
        {
            head = current;
            current->next = previousTop;
            return;
        }
 
        // Initialize 'NEXT_TO_CURRENT' pointer with CURRENT->NEXT.
        Node *nextToCurrent = current->next;
 
        // Redirect 'NEXT' pointer of the 'CURRENT' node.
        current->next = previousTop;
 
        // Call the recursive function with 'NEXT_TO_CURRENT' and 'CURRENT' parameters.
        reverseLinkedListHelper(nextToCurrent, current);
    }
 
    void reverseLinkedList()
    {
 
        // If 'HEAD' is not pointing to any node, list is empty.
        if (!head)
            return;
 
        // Set 'CURRENT' node equal to first node of the linked list.
        Node *current = head;
 
        /*  Set 'PREVIOUS_TOP' node to NULL to represent
            end of the linked list after reversal.
        */
        Node *previousTop = NULL;
 
        // Call helper function to reverse the linked list.
        reverseLinkedListHelper(current, previousTop);
 
        // Print the reversed linked list.
        printLinkedList();
    }
};
 
int main()
{
    int totalNodes;
    cout << "Enter the number of nodes in the linked list: ";
    cin >> totalNodes;
 
    cout << "Enter the data of nodes: ";
    LinkedList *givenList = new LinkedList();
    for (int i = 0; i < totalNodes; i++)
    {
        int data;
        cin >> data;
        givenList->insert(data);
    }
    cout << "Reversed linked list: ";
    givenList->reverseLinkedList();
}

Input

Enter the number of nodes in the linked list: 4
Enter the data of nodes: 1 2 3 4

Output

Reversed linked list: 4 3 2 1

Complexity Analysis

Time Complexity: Traversal through the linked list is required to reverse the pointers of the linked list nodes. Traversal through the linked list is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

Space Complexity: The recursion stack space requires O(N) space.

Skimming through blogs can be perplexing at times, so let's watch a video to quickly learn how to reverse a Linked List - Iteratively & Recursively.

Frequently Asked Question(FAQs)

What is the time complexity for reversing a Linked List?

The time complexity for reversing a Linked List is O(N) where N is the length of the Linked List.

What are linked lists used for?

Linked lists are linear collections of data elements stored randomly in the memory. They allow efficient insertion and deletion and can implement queues, stacks, and other abstract data types.

Why do we need to reverse a linked list?

The node’s next property determines the order in a singly linked list. This could either refer to another node or point to null if it is the last node in the list. Reversing a linked list, therefore, refers to reassigning all the next properties on every node.

Conclusion

Reversing a linked list may look like a simple operation. However, the applications of linked list reversal are vast. Many algorithms related to linked lists are based on the linked list reversal. It’s great that you have learned it now. But don’t just stop your learning journey here. Head over to Coding Ninjas Studio to make your learning easy, interesting, and efficient. Coding Ninjas Studio offers interesting blogs, inspirational interview experiences, and much more.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Topics covered
1.
Introduction
2.
Problem Statement
3.
Method 1: Stack
3.1.
Algorithm
3.2.
Program
3.3.
Complexity Analysis
4.
Method 2: Iteration with constant space
4.1.
Algorithm
4.2.
Program
4.3.
Complexity Analysis
5.
Method 3: Recursion with constant space
5.1.
Algorithm
5.2.
Program
5.3.
Complexity Analysis
6.
Frequently Asked Question(FAQs)
6.1.
What is the time complexity for reversing a Linked List?
6.2.
What are linked lists used for?
6.3.
Why do we need to reverse a linked list?
7.
Conclusion