Reverse Linked List Leetcode Problem 206 [Python]

In the world of data structures and algorithms, understanding how to reverse a linked list is a fundamental skill.

This problem often serves as a building block for more complex linked list-related challenges.

In this guide, we’ll explore the Reverse Linked List problem on LeetCode, specifically Problem 206. We’ll delve into two efficient solutions: one implemented iteratively and the other recursively.

By the end of this post, you’ll have a solid grasp of how to tackle this problem, making you better equipped to handle other linked list challenges.

Problem Overview

The task at hand is clear: given the head of a singly linked list, we need to reverse the list and return the reversed version.

The input is a linked list, and the output should be the reversed linked list.

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: []

Understanding the Constraints

Before diving into the solution, let’s grasp the constraints of this problem.

This is crucial, especially for beginners, as it helps in designing efficient algorithms.

In this case:

• The number of nodes in the list can range from 0 to 5000.
• The values of the nodes fall within the range of -5000 to 5000. Additionally, there’s a follow-up challenge: the reversal of a linked list can be accomplished iteratively or recursively.

We’ll tackle both methods, ensuring that you have a well-rounded understanding of the problem.

Reverse Linked List LeetCode Problem Solution

Let’s get into the details of how to solve this problem using both an iterative approach and a recursive approach.

1. Iterative Approach

We’ll start with an efficient iterative solution.

In this approach, we’ll use two pointers, current and previous, to reverse the links in the linked list.

The algorithm works as follows:

1. Initialize current to the first node, which is the head, and set previous to None.
2. While current is not None (i.e., we haven’t reached the end of the list), do the following:

• Create a temporary variable, temp, and store the next node in it.
• Update current.next to point to previous, effectively reversing the link.
• Shift previous to current and current to temp.

1. Once the loop ends, previous points to the new head of the reversed list.

Return previous.

Here’s the Python code that implements this iterative approach:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        return prev

This is the most optimal solution for this problem.

Its time complexity is O(n), and it has a memory complexity of O(1) since it uses only pointers and doesn’t require additional data structures.

2. Recursive Approach

Now, let’s explore the recursive approach.

Recursive solutions are elegant but come with a trade-off of increased memory usage.

The idea here is to break down the problem into smaller subproblems.

To reverse a linked list recursively, we perform the following steps:

1. Base Case: If the current node (head) is None, return None as there’s nothing to reverse.
2. Recursive Step: Recursively reverse the rest of the list.

This is essentially reversing the linked list without the current node.

3. After the recursive call returns, we’ll be at the last node in the list.

To reverse the current node, set head.next.next to head (reverse the link).

4. Finally, set head.next to None to terminate the original list.

Here’s the Python code implementing the recursive solution:

View on GitHub ➹
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return new_head