Reverse a Linked List

Given Linked List

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

Read the problem description for more detail. 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 it's previous node. Let's visualize the process step by step

Intuition & Pointer Placement

To solve this problem we are taking Two Pointers one is prev initially pointed to out of the Linked List (i.e. NULL) and another one is curr which is pointing at the HEAD of the Linked List.
We will curr pointer to connect the current node to it's adjacent previous node like this.

prev = None
curr = head
curr.next = prev

Let's visualize the outcome of the above code snippet.

So we can see the current node is pointing to it's immediate previous node but we need to keep doing this until the curr pointer reaches at the end of the Linked List (i.e. NULL). So the curr and prev both needs to move forward.

But how the curr can move to it's next node? We just have modified curr.next

Reverse Links Iteratively

Before modifying .next we need to save the reference in a temporary variable. Let's say curr_next Let's take a look at the code is pretty simple actually

prev = None
curr = head
while curr:
	# saving next node of the curr for further progress of curr pointer
	curr_next = curr.next
	curr.next = prev
	prev = curr  # moving prev forward
	curr = curr_next  # moving curr forward
return prev  # new reversed head

Let's visualize the whole outcome of this code snippet

As the curr reached to the end of the Linked List that means all the Nodes by now are pointing to their adjacent previous Nodes.

Complete Code Snippet

Let's take a look at the complete code snippet bellow

class Solution(object):
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		prev = None
		curr = head
		while curr:
			curr_next = curr.next
			curr.next = prev
			prev = curr
			curr = curr_next
		return prev

That's all for today. We can also solve this problem using recursion but the iterative approach is more optimal solution.

Complexity Analysis

Time Complexity is O(N) where N is the number of nodes in the Linked List.
The Space Complexity is Constant means No extra space.

But if we solve this problem recursively Reverse a Linked List (Recursive), the recursion maintains a Call Stack which would take additional O(N) space complexity which is not taking by iterative approach.

Thanks for Stopping by! Happy Leet coding.

Connect with me on