Reverse Linked List

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

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
  1. The number of nodes in the list is the range [0, 5000].
  2. -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:

  1. previous_node is set to None as there’s no node before the head in the reversed list yet.
  2. current_node is set to the head node of the input list.
  3. next_node is initially None.
				
					previous_node = None
current_node = head
next_node = None

				
			

3. Reversing the List

  1. Inside the while loop, the code iterates through the list until current_node becomes None, indicating the end of the list.
  2. For each iteration:
    1. next_node stores the reference to the next node in the original list (current_node.next).
    2. current_node.next is set to previous_node, reversing the pointer direction.
    3. previous_node is updated to current_node (shifts the reference for the next iteration).
    4. 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:

  1. Once the loop completes, previous_node holds the new head of the reversed list.
  2. head (the original parameter) is updated to point to this new head (previous_node).
  3. 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

Leave a Reply

Your email address will not be published. Required fields are marked *

Welcome to our diverse learning options!

Select the learning format that suits your preferences and schedule.