Leetcode – Reverse Linked List Solution in Python

Spread the love

Introduction

Reversing a linked list is a classic algorithmic problem often asked in coding interviews and present on competitive programming platforms like LeetCode. Being proficient in manipulating linked lists is essential for anyone delving into computer science and programming. This article aims to provide an in-depth look at the Reverse Linked List problem on LeetCode, various approaches to solve it, and Python code implementations.

Problem Description

The Reverse Linked List problem (LeetCode #206) is defined as follows:

Reverse a singly linked list.

Example: Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

A linked list is a data structure where each element points to the next one. The task is to reverse the pointers so that the last element points to the second last, and so on.

Understanding Linked Lists

A singly linked list consists of nodes, where each node contains a data element and a pointer to the next node in the list. The first node is called the head of the list, and the last node points to NULL, indicating the end of the list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Approach 1: Iterative Method

The most common method to reverse a linked list involves using an iterative approach where we use three pointers: prev, curr, and next. We traverse the list and reverse the pointers iteratively.

def reverseList(head):
    # Initialize pointers
    prev = None
    curr = head
    
    # Traverse the list
    while curr:
        # Keep track of the next node
        next = curr.next
        # Reverse the current node's pointer
        curr.next = prev
        # Move pointers one position ahead
        prev = curr
        curr = next
    
    return prev

This approach has a time complexity of O(n) and a space complexity of O(1).

Approach 2: Recursive Method

Another approach to reverse a linked list is to use recursion. In this method, we recursively reverse the sub-list leaving the first element and then reverse the pointer of the first element.

def reverseList(head):
    # Base case
    if not head or not head.next:
        return head
    
    # Recursive case
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    
    return new_head

The recursive approach also has a time complexity of O(n), but the space complexity is O(n) due to the recursive call stack.

Approach 3: Using a Stack

We can also reverse a linked list by using a stack. We can traverse the original linked list and push each node onto a stack. We then pop elements from the stack, which will be in reversed order, and create a new linked list.

def reverseList(head):
    # Edge case
    if not head:
        return None
    
    # Using a stack to reverse nodes
    stack = []
    while head:
        stack.append(head)
        head = head.next
    
    # Creating a new linked list from the stack
    new_head = stack.pop()
    current = new_head
    while stack:
        current.next = stack.pop()
        current = current.next
    
    # End the new linked list
    current.next = None
    
    return new_head

This approach has a time complexity of O(n) but uses O(n) space due to the stack.

Conclusion

Reversing a linked list is a fundamental problem that helps in understanding the manipulation of pointers and linked list data structure. We discussed three different approaches to solving the Reverse Linked List problem on LeetCode – iterative, recursive, and using a stack. The iterative method is often preferred due to its constant space complexity. However, understanding different methods is essential for developing versatile problem-solving skills.

Leave a Reply