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.
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.