Reverse Linked List (Leet code -206)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 206. This is a Leet code problem named Reverse Linked List. We will solve it using python and it is the best space and time-optimized solution.

Question of Reverse Linked List

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

In this question, we have to reverse the given linked list. Suppose we have a linked list like the below:

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

In the above linked list head node is 1 and the tail node is 5. So we simply have to reverse that and after reversing our head node will be 5 and tail node will be 1. It will look like this:

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

Example

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

Recursive Approach to solve Reverse Linked List

To solve this question we will solve it using the recursive method. In the recursive approach, we will call the same function. First, we separate the list into two sections: the initial node and the remaining linked list. After that For the remaining connected list items, we call the reverse function again. We will repeat this until we reach the end of the node. Then while backtracing the remainder is connected to the beginning. And we fix the head pointer.

So while doing this our list will be reversed and new head will be last node which we wanted.

Algorithm

This method performs the following steps for a given input array:

Check the base condition i.e. if the head is Nonne then return the head.
Now we reverse the rest of the list i.e. calling step 2 for the remaining list.
Now we put the first element at the end.
Assign Next of next of head to head
Assign next of head to None
Return the rest pointer.

Python Code to Reverse Linked List

# 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: Optional[ListNode]) -> Optional[ListNode]:
        
        #Check the base condition i.e. if the head is Nonne then return the head
        if head is None or head.next is None:
            return head
 
        # Reverse the rest list
        rest = self.reverseList(head.next)
 
        # Put the first element at the end
        head.next.next = head
        head.next = None
 
        # Fix the header pointer
        return rest

Iterative Approach to solve Reverse Linked List

In an iterative approach, we will iterate through the whole linked list. While iterating we will swap the next of the current node.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #to store head of previous node
        prev = None
        #current node while traversing
        cur = head
        #iterate in linked list
        while cur:
            #assign nxt to next of current
            nxt = cur.next
            #assign next of current to previous
            cur.next = prev
            #assign previous to current
            prev = cur
            #assign current to next
            cur = nxt
        return prev