menu

### Reverse Linked List

**Problem Statement:** Given the head of a singly linked list, reverse the list, and return the reversed list.

##
Examples

##### Example 1

Input:head = [1,2,3,4,5]Output:[5,4,3,2,1]

##### Example 2

Input:head = [1,2]Output:[2,1]

##### Example 3

Input:head = []Output:[]

##### Constraints

- The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

### Solution

Below is the solution in interative approach.

` ````
```# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head):
previous_node = None
current_node = head
next_node = None
while current_node:
next_node = current_node.next
current_node.next = previous_node
previous_node = current_node
current_node = next_node
head = previous_node
return head

##### Explanation

**1. Function Definition**

We have a class `Solution`

that contains a method `reverseList`

which takes in a `head`

node of a singly-linked list.

` ````
```class Solution:
def reverseList(self, head):

**2. Initialization**

Three pointers are initialized:

`previous_node`

is set to`None`

as there’s no node before the head in the reversed list yet.`current_node`

is set to the`head`

node of the input list.`next_node`

is initially`None`

.

` ````
```previous_node = None
current_node = head
next_node = None

**3. Reversing the List**

- Inside the
`while`

loop, the code iterates through the list until`current_node`

becomes`None`

, indicating the end of the list. - For each iteration:
`next_node`

stores the reference to the next node in the original list (`current_node.next`

).`current_node.next`

is set to`previous_node`

, reversing the pointer direction.`previous_node`

is updated to`current_node`

(shifts the reference for the next iteration).`current_node`

is updated to`next_node`

(moves to the next node in the original list).

` ````
```while current_node:
next_node = current_node.next
current_node.next = previous_node
previous_node = current_node
current_node = next_node

**4. Final Steps:**

- Once the loop completes,
`previous_node`

holds the new head of the reversed list. `head`

(the original parameter) is updated to point to this new head (`previous_node`

).- Finally, the updated
`head`

representing the reversed list is returned.

` ````
```head = previous_node
return head

This algorithm uses three pointers to manage nodes in the original list while changing their connections to create the reversed list. It reverses the linked list in linear time complexity (O(n)), where ‘n’ is the number of nodes in the list, without requiring additional space.

WhatsApp

Facebook

Twitter

LinkedIn

Email