Reverse Linked List | LeetCode 206 | Python | Solution

LeetCode 206

Reverse Linked List is one of the classic programming problems.

The problem description is nothing complicated. We have to reverse the given Linked List and return the reversed list.

For example:

1 -> 2 -> 3
     ↓
3 -> 2 -> 1

We can solve this problem in many ways. Before getting into the solution, you can check my blog about the Linked List data structure if you need it.

A brute-force solution can be like this: First, we will store all nodes in an array. Then we will reverse it using a built-in reverse function. And after that, create a new linked list from that reversed version array’s elements.

Let’s see the code.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        lst = []
        
        while head:
            lst.append(head.val)
            head = head.next
        
        lst.reverse()
        
        head = ListNode(-1)
        curr = head
        
        for el in lst:
            curr.next = ListNode(el)
            curr = curr.next
        
        return head.next

The above solution will get accepted. But there is a better solution than this.

As the given list will be singly linked list, we can’t go backward from a node. If it were, we could get reversed version from traversing backward from the last node.

But this time we can’t do this. We only have the option to go forward. So, we can solve this problem by changing the direction of each node.

Suppose The head node will be the last in the reversed version, and it will point to None/null. So, we will change the head node’s next pointer to None instead of pointing to the second node.

At the same time, we will lose the connection of the head node from the given list. And it’s okay. In the meantime, we also need to keep track of the original list. For that, before changing the direction of the head, we will store the head’s next node in a variable. And we also have to keep track of the last direction-changing node.

Now, we will change the direction of the second node. This node will be in the second last position in the reversed version. So, it will point to the last node, and at this point, the head is the last one. At the same time, the second node will also lose the connection from the third. And it’s also okay. Before changing the direction of the second node, we will store the second’s next node.

We will continue to do this until we reach the end of the given list. We have to keep track of the very last changed node each time. So that we can get the new head after ending the process, which is the last node of the given linked list.

1 -> 2 -> 3 -> None

Step One
2 -> 3 -> None
None <- 1 

Step Two
3 -> None
None <- 1 <- 2

Step Three
None
None <- 1 <- 2 <- 3
Stop the process

3 -> 2-> 1 -> None

Let’s see the solution in Python.

# 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]:
        
        previous = None
        current = head
        
        while current:
            
            next = current.next
            current.next = previous
            previous = current
            
            current = next
        
        return previous

I hope you got the idea of the problem and solution. Though, it’s a bit tough to explain this in text-based content. Even then, I hope you will find something beneficial.

Happy Learning.
Happy Coding.

Tags: LeetCodeLinked ListProblem SolvingSolution