## 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!

## Leave a Reply