Reverse a Linked List (Recursive)

Given Linked List

Need to reverse the given linked list which will eventually look like this.

Read the problem description for more detail.

Intuition

Before solving the problem let's think how a Linked List can be reversed. Simple by reversing the connected link, more technically by modifying the .next pointer. Instead of pointing the next node .next pointer will point to it's previous node.

The Idea is Starting from the Head, we will reach at the Last Node (you can say bottom) of the Linked List and start reversing from there. Let's take a variable called revHead which is going to be the Head of our final Reversed Linked List.

class Solution(object):
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		revHead = head

What will happen when the function got executed?
So the main function has called our reverseList function and it looks like this from the view of call stack

Going into the Depth

As you can see our current Head is 1 which has a non null node next to it. So we can call reverseList with the next node of the current Head like reverseList(head.next). We can keep doing this until the Head has Non Null Next Node.

class Solution(object):
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		revHead = head
		if head.next:
			revHead = self.reverseList(head.next)

Let's visualize the recursion call-stack.

Okey, We just stepped onto the Last Node of the Linked List 3. So there will be no further recursion call. Now look at the Actual Linked List once again now.

Pull up Reversed Head and Reverse Nodes Right to Left

We are at the Last Node and the Last Node has no one except NULL next to it, meaning nothing to reverse. Just connect the Head with NULL, you will see the reason shortly. Also we will return the revHead (reversed head) to it's previous call from the call-stack.

class Solution(object):
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		revHead = head
		if head.next:
			revHead = self.reverseList(head.next)
			# reverseList(3) will return here with revHead=3
			# so we are at reverseList(2) where 
			# head = 2
			# head.next = 3
			# so we need to reverse the link here. 
			# we will see this process in the visual next
			rightNode = head.next
			# now rightNode is like 3 -> None
			rightNode.next = head
			# so now the 3 -> 2, 
			# though node 2 still pointing to node 3, like 3 <- 2
			# but that will be fixed in the next like
		
		# fixing the next of current head
		head.next = None
		return revHead

Let's visualize this code

Have you noticed We are updating Reverse Head from it's previous call. It's just to keep track of the Reverse Head in every state, kind off Pulling Up 💪 an Anchor ⚓️ from the deep 🌊 😎
Meanwhile We also done reversing the .next pointer between the Pairs of Node.
So we can just return the reversed head to call it done.

Complete Code Snippet

class Solution(object):
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		# adding a safety check incase the given head itself is null
		if not head:
			return None
		
		# initializing the reversed head with the head .
		# it will be reinitialized by teh current head of every recursion call
		revHead = head
		
		# we will keep recursing until we step onto the last node
		if head.next:
			# recursion call with the next node
			revHead = self.reverseList(head.next)
			# connecting right node with head (left node)
			rightNode = head.next
			rightNode.next = head
		
		# connecting current head (left node) with None
		head.next = None
		return revHead

Complexity Analysis

Time Complexity is O(N) where N is the number of nodes in the Linked List.
The Space Complexity is O(N) since there is N number of calls in the call-stack. Because, the recursion maintains a Call Stack which would take additional O(N) space

So solving Reverse a Linked List in iterative approach is the Optimal Solution for this. Because, that will take only O(N) Time Complexity with no additional space complexity.

Thanks for Stopping by! Happy Leet coding.

Connect with me on