Java Program to Reverse a Linked List

Nishant Rana
Last Updated: May 13, 2022

Introduction:

We are given the head of the Linked List. We need to reverse the Linked List.

 

Input 1: 

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

 

Output 1:

NULL <- 1 <- 2 <- 3 <- 4 <- 5

 

Input 2:

1 -> NULL

 

Output 2:

1 -> NULL

 

Approach 1(Iterative Approach):

We will first discuss the Iterative Approach to reverse the Linked List. We will be maintaining the following three pointers:-

  1. current: This pointer will point to the current node we are at.
  2. prev: This pointer will point to the previous node of the current node. We will assume the previous of the Head node to be NULL.
  3. next: This pointer will point to the next of the current node.

 

We will use the prev pointer to update the next of the current node to be the previous node because this is what we will have when we reverse the Linked List.

 

We are maintaining the next pointer because once we update the next of the current node to be the previous node, we must have the access to the next of the current node to move to the next node.

 

Refer to the below implementation of the above approach.

 

Node reverse(Node head) {
    
    //Initializing our three pointers.
    Node prev = null;
    Node current = head;
    Node next = null;
    
    /*
      Running a for loop to 
      update the next pointer
      of all the nodes.
    */
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    /*
      Last node is the head
      of the newly reversed
      Linked List
    */
    node = prev;
    return node;
}

 

Time Complexity: The time complexity for the above approach is O(N) (where ‘N’ is the number of nodes in the Linked List) because we are just iterating the Linked List once.

 

Space Complexity: The space complexity of the above approach is O(1) because we are using the constant auxiliary space.

 

Approach 2 (Recursive Approach):

We will apply a similar approach to the Iterative Approach to reverse the Linked List using the prev, current, and next1 pointers. We will pass the current and the prev pointer to our recursive function. When we make a recursive call, we will pass the next node as the current node and the current node as the prev node.

 

Refer to the below implementation of the above approach.

 

Node reverse(Node curr, Node prev) {
  
        //Base case
        if (curr.next == null) {
            
            /*
              Updating the next 
              of the current node 
              to prev.
            */
            curr.next = prev;
            return curr;
        }
  
        /*
          Storing the next of 
          the current node for 
          the next recursive call
        */
        Node next1 = curr.next;
  
        /*
          Updating the next 
          of the current node 
          to prev.
        */
        curr.next = prev;
  
        return reverse(next1, curr);
}

 

Time Complexity: The time complexity for the above approach is O(N) (where N is the number of nodes in the Linked List) because we are just iterating the Linked List once.

 

Space Complexity: The space complexity of the above approach is O(1) because we are using the constant auxiliary space.

 

FAQs:

  1. What are prev, current, and next pointing to when we reverse the Linked List?
    • current: This pointer will point to the current node we are at.
    • prev: This pointer will point to the previous node of the current node. We will assume the previous of the Head node to be NULL.
    • next: This pointer will point to the next of the current node.

 

2. What is the time complexity for the approach we have used to reverse the Linked List?

  • The time complexity for the approach to reverse the Linked List is O(N) (where N is the number of nodes in the Linked List) because we are just iterating the Linked List once.

 

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the Iterative approach to reverse the Linked List.
  2. Then we discussed the Recursive approach to reverse the Linked List.

 

If you want to learn more about Linked List and want to practice some questions which require you to take your basic knowledge on Linked List a notch higher, then you can visit our Guided Path for Linked List. To practice this problem, you can visit Practice Problem.

 

Until then, All the best for your future endeavors, and Keep Coding.










 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think