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