# Leetcode – Reverse Linked List Solution in Python

## 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:

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.

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

# 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

# Recursive case

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
return None

# Using a stack to reverse nodes
stack = []

# Creating a new linked list from the stack
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.