Reverse a Linked List

Posted in

Reverse a Linked List

Vinay Khatri
Last updated on June 10, 2022

    Linked List is one of the most important data structures in computer science due to several reasons. The most important one is the drawbacks of the array data structure. Deletion of the elements of the array data structure is highly in-efficient and requires a very time-consuming process. Linked list overcomes this drawback as well as many other drawbacks of the array data structure with the help of concepts such as pointers and references. In this article, we will discuss how to reverse a singly linked list using two approaches.

    Reverse Singly Linked List

    Given a Singly Linked list containing n number of predefined nodes, the main task is to reverse the linked list without using any other linked lists.

    Input:  1->2->3->4->5->null
    Output: 5->4->3->2->1->null
    
    Input: null
    Output null
    
    Input: 2->null
    Output 2->null

    Approach 1: Simple Iterative Approach

    This approach is a little tricky. In this approach, we use three-pointers or three references.

    • Iterate the original Linked List using for loop or while loop and do the following operations.
    • Store the current.next element in one reference or pointer of the node.
    • Change the current.next reference/pointer to the second reference.
    • Update the second reference/Pointer with the current element.
    • Update the current reference/Pointer.

    Java:

    //Importing Libraries
    import java.util.*;
    import java.io.*;
    class Main{
        //Creating head reference of the linked list
        static Node head;
        //Creating static class of the linked list
        static class Node{
            int data; //Data to be stored in the node of the linked list
            Node next; //Reference of the node in the linked list
            //Constructor of the static class
            public Node(int data){
                this.data=data;
            }
         }
        //Function to insert the node in the linked list 
        static void push(int data){
            if(head==null){
                //Insert the head if the linked list is null
                head=new Node(data);
            }
            else{
    
                Node temp=head;
                //Iterate the linked list 
                while(temp.next!=null){
                    temp=temp.next;
                }
                temp.next=new Node(data);
            }
        }
        //Function to print the linked list
        static void print(Node head){
         Node temp=head;
         while(temp!=null){
             //Printing the data of the node
             System.out.print(temp.data+" ");
             //Increment the node of the linked list
             temp=temp.next;
         }
         System.out.println();
        }
        //Function to reverse the linked list
       static Node reverse(Node head){
           Node current=head;
           //Creating two reference 
            //First reference
           Node previous_node=null;
          
           Node previous_previous_node=null;
           while(current!=null){
               //Store the current.next reference
               previous_node=current.next;
               //Initialize the current.next last previous node
               current.next=previous_previous_node;
               //Update the last previous node current element
               previous_previous_node=current;
               current=previous_node;
           }
            //Return the reversed Linked list
           return previous_previous_node;
       }
        public static void main(String[] args) {
         //Creating Head of the linked list
         push(1);
         //Creating second node of the linked list
         push(2);
         //Creating third node of the linked list
         push(3);
         //Creating fourth node of the linked list
         push(4);
         //Creating fifth node of the linked list
         push(5);
         System.out.println("Original Linked List");
         print(head);  
         System.out.println("Reversed Linked List");
         Node head_reversed=reverse(head);
         print(head_reversed);     
        }
    }
    

    Output: Python:

    #Creating Node class 
    class Node:
        #Creating Constructor
        def __init__(self,data):
            self.data=data #Creating data to be stored in the node of the linked list
            self.next=None #Creating next reference of the node 
    #Creating class of Linked class        
    class LinkedList:
        #Creating Constructor
        def __init__(self):
            self.head=None
        #Funcion to insert new node in the linked list
        def insert(self,data):
            #Checking if head is not None
            if self.head is None:
                self.head=Node(data)
            else:
                last=self.head
                while(last.next):
                    last=last.next
                #Insert last node in the linked list    
                last.next=Node(data)
        #Function to print the Linked list
        def print(self):
            #Creating temp reference of the head
            temp=self.head
            LinkedList=[]
            #Iterate the Linked list
            while(temp is not None):
                #Storting the node data in the list
                LinkedList.append(temp.data)
                temp=temp.next
            #Printing the list    
            print(LinkedList) 
        #Function to  reverse the Linked list       
        def reverse(self):
            #Creating two reference 
      
            current=self.head
            #First reference
            previous=None
            #Second reference
            previous_previous=None
            while(current is not None):
                #Store the current.next reference
                previous=current.next
                #Initialize the current.next last previous node
                current.next=previous_previous
                #Update the last previous node current element
                previous_previous=current
                current=previous
            self.head=previous_previous 
    list=LinkedList()
    #Inserting First Node in the Linked List
    list.insert(1)
    #Inserting Second Node in the Linked List
    list.insert(2)
    #Inserting Third Node in the Linked List
    list.insert(3)
    print("Original Linked List")
    list.print()   
    
    list.reverse()
    #Printing Reversed Linked List
    print("Reversed Linked List")
    list.print()
    

    Output: C++:

    //Importing all the required libraries
    #include<bits/stdc++.h>
    using namespace std;
    //Creating structure for the node of linked list
    struct Node{
    int data;//data to be stored to the node in the linked list
    
    Node*next;//next reference to the node in the linked list
    //Creating Constructor
    Node(int data){
    this->data=data; //Storing the data to the node
    this->next=nullptr;
    
    }
    };
     //Function to Transverse the Linked list
    void print(Node *head){
         //Checking if the Linked list is null or not
         Node *temp=head;
        if(temp==NULL){
            return;
        }
      //Transverse the Linked List
    while(temp!=NULL){
    cout<data<<" "; temp=temp->next;
    }
    
    }
    //Function reverse the linked list
    Node* reverse_LinkedList(Node *head){
        //Creating two pointers
        Node *current=head;
        //First pointer
        Node *previous=NULL;
        //Second pointer
        Node *previous_previous=NULL;
        while(current!=NULL){
            //Store the current->next reference    
            previous=current->next;
           //Update the last previous node 
            current->next=previous_previous;
            //Update the last previous node
            previous_previous=current;
            current=previous;
        }
        
         head=previous_previous;
         //Returning the Reversed Linked list
         return head;
    }
    
    int main(){
    //Creating Head of the linked list
    Node *head =new Node(10);
    //Creating Second node of the linked list
    head->next=new Node(11);
        //Creating third node of the linked list
    head->next->next=new Node(12);
    //Printing Original Linked List
    printf("Original Linked List\n");
    
    print(head);
    printf("\n");
    //Printing Reversed Linked List
    printf("Reversed linked list\n");
    Node * head1=reverse_LinkedList(head);
    print(head1);
    
    return 0;
    
    }
    

    Output: Complexity:

    • Time Complexity : The Time complexity of this approach is O(n).
    • Space Complexity : The Space Complexity of this approach is O(1).

    Approach 2: (Recursive Approach)

    In this approach, we will use recursion to reverse the original linked list.

    • Divide the Linked list into two halves, the first node and the remaining nodes of the original list.
    • Call recursive function and link the remaining Linked list to the first node of the original linked list.
    • At last the change the head Pointer/Reference of the Linked List.

    Java

    //Importing Libraries
    import java.util.*;
    import java.io.*;
    class Main{
        //Creating head reference of the linked list
        static Node head;
        //Creating static class of the linked list
        static class Node{
            int data; //Data to be stored in the node of the linked list
            Node next; //Reference of the node in the linked list
            //Constructor of the static class
            public Node(int data){
                this.data=data;
            }
         }
        //Function to insert the node in the linked list 
        static void push(int data){
            if(head==null){
                //Insert the head if the linked list is null
                head=new Node(data);
            }
            else{
    
                Node temp=head;
                //Iterate the linked list 
                while(temp.next!=null){
                    temp=temp.next;
                }
                temp.next=new Node(data);
            }
        }
        //Function to print the linked list
        static void print(Node head){
         Node temp=head;
         while(temp!=null){
             //Printing the data of the node
             System.out.print(temp.data+" ");
             //Increment the node of the linked list
             temp=temp.next;
         }
         System.out.println();
        }
        //Function to reverse the linked list
       static Node reverse(Node head){
           //Checking the base condition
         if(head==null||head.next==null){
             return head;
         }
         //Recursively call the remaining Linked list
         Node small=reverse(head.next);
           //Update the head of the Linked List
           //Reverse the two nodes
           head.next.next=head;
           //Update the head pointer/Reference
           head.next=null;
           return small;
       }
        public static void main(String[] args) {
         //Creating Head of the linked list
         push(1);
         //Creating second node of the linked list
         push(2);
         //Creating third node of the linked list
         push(3);
         //Creating fourth node of the linked list
         push(4);
         //Creating fifth node of the linked list
         push(5);
         System.out.println("Original Linked List");
         print(head);  
         System.out.println("Reversed Linked List");
         Node head_reversed=reverse(head);
         print(head_reversed);     
        }
    }
    

    Output: C++:

    //Importing all the required libraries
    #include
    #include
    #include<bits/stdc++.h>
    using namespace std;
    //Creating structure for the node of linked list
    struct Node{
    int data;//data to be stored to the node in the linked list
    
    Node*next;//next reference to the node in the linked list
    //Creating Constructor
    Node(int data){
    this->data=data; //Storing the data to the node
    this->next=nullptr;
    
    }
    };
     //Function to Transverse the Linked list
    void print(Node *head){
         //Checking if the Linked list is null or not
         Node *temp=head;
        if(temp==NULL){
            return;
        }
      //Transverse the Linked List
    while(temp!=NULL){
    cout<data<<" "; temp=temp->next;
    }
    
    }
    //Function reverse the linked list
    Node *reverse_LinkedList(Node *head){
        //Checking the base condition
        if(head->next==NULL||head==NULL){
            return head;
        }
        //Recursively call the remaining node of the linked list
        Node* remaining=reverse_LinkedList(head->next);
        //Update the reference of the head pointer
        head->next->next=head;
        head->next=NULL;
        return remaining;
    }
    
    int main(){
    //Creating Head of the linked list
    Node *head =new Node(10);
    //Creating Second node of the linked list
    head->next=new Node(11);
        //Creating third node of the linked list
    head->next->next=new Node(12);
    //Printing Original Linked List
    printf("Original Linked List\n");
    
    print(head);
    printf("\n");
    //Printing Reversed Linked List
    printf("Reversed linked list\n");
    Node * head1=reverse_LinkedList(head);
    print(head1);
    
    return 0;
    
    }
    

    Output: Python:

    #Creating Node class
    class Node:
        def __init__(self,data):
             self.data=data #Creating data of the node
             self.next=None #Creating next reference of the node of the linked list
    #Creating Linked List        
    class LinkedList:
        #Creating Linked List class constructor
        def __init__(self):
            self.head=None
        #Function to push the node in the linked list
        def push(self,data):
            node=Node(data)
            node.next=self.head
            self.head=node #Update the head pointer
        #Function to reverse the Linked list    
        def reverse(self,head):
            #Checking the head of the linked list
            if head is None or head.next is None:
                return head
            #Recursively call the  remaining node of the linked list    
            remaining=self.reverse(head.next)
            #Update the head reference in the linked list
            head.next.next=head
            head.next=None
            #Return the Reversed Linked List
            return remaining
        #Function to print the LinkedList        
        def printList(self):
            temporary_List=self.head
            List=[]
            #Iterate the Linked List
            while(temporary_List):
                #Add the node value to the list
                List.append(temporary_List.data)
                temporary_List=temporary_List.next
            #Print the List    
            print(List)    
    #Creating List reference of the Linked List
    List=LinkedList()
    #Inserting node in the Single list
    List.push(1)
    List.push(2)
    List.push(3)
    #Printing the original linked list
    print("Original Linked List")
    List.printList()        
    #Printing the reversed Linked List
    print("Reversed Linked List")
    List.head=List.reverse(List.head)
    List.printList()

    Output:

    Conclusion

    Reversing a Linked List is one of the most interesting problems of Data structure. In this article, we have discussed two approaches to Reverse a linked list. One approach is using a simple iteration with three-pointers/reference concepts and a second approach is a recursive approach. There are so many interesting projects that can be easily made using the concept of Reversing a Linked list and the most common example is Snake Game . We hope this article will help you to understand the problem statement and you will be able to solve any other variation of this problem. Happy Coding! People are also reading:

    Leave a Comment on this Post

    0 Comments