Data Structures & Algorithms in Java – Linked List – Reverse Linked List

Problem:

Given the head of a singly linked list , reverse the list and return the new head of the reversed list.

For example :

[1,2,3,4,5] – the array represents the node with 1 as the head node

Output should be

[5,4,3,2,1]

Visual representation:

Try out the solution here:

https://leetcode.com/problems/reverse-linked-list/

Solution:

Hint:

• Make the second node point to the first node and the third node point to the second node and so on until there is no more nodes

The solution looks pretty straightforward but the pointing can be a bit confusing to understand.

You can do it in the following way

• Create a new node

• Create a node next which points to the second one initially (next of head node)
• Make the next of head node point to the new node
• Make the new node point to the first node
• Make the first node point to the next node

At the end of these steps the pointers would have reversed.

Now you need to continue this until head becomes null (next node of the last node).

When head becomes null the “new node” will become the new head node of the reversed linked list.

In short , you keep incrementing the head node and make it point to the “new node”. When you reach the end of the list head becomes null and “new node” becomes the head.

ALGORITHM:

STEP 1: Create a blank new node

STEP 2: while head node is not null do the following

STEP 2a: Create a node next which points to the next node of head

STEP 2b: Make the next of head node point to the new node

STEP 2c: Make the new node point to the head node

STEP 2d: Make the head node point to the next node created in step 2a

STEP 3: Return the new node

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode newNode = null;
        
        while(head != null){
            
            
            ListNode next = head.next;
            head.next = newNode;
            newNode = head;
            head  = next;
        }
        
        return newNode;
    }
}

If you notice in the above code at the end of each loop the head node becomes the new node and the next node becomes the head node.

So you can refactor the code recursively as below:

 /**
 public class ListNode {
     int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     

  }
  
  **/
 
class Solution {
    public ListNode reverseList(ListNode head) {
      
            //initially new node is null
            return recursive(head,null);
        
    }
    
    public ListNode recursive(ListNode head,ListNode newNode){
        
        
        if(head == null) return newNode;
        
        
        ListNode next = head.next;
        
        head.next = newNode;
        
//   next node becomes the head node and head node becomes the new node
        return recursive(next,head);
        
    }
}

That’s it!