# Reverse Linked List - LeetCode Problem

## Problem Description

Welcome back! Today, we'll be solving the [Reverse Linked List problem](https://leetcode.com/problems/reverse-linked-list/) on LeetCode.

Given the `head` of a singly linked list, reverse the list, and return the reversed list's `head`.

For example, if the input linked list is `1 -> 2 -> 3 -> 4 -> 5 -> NULL`, then the output linked list should be `5 -> 4 -> 3 -> 2 -> 1 -> NULL`.

That's a fun problem to solve! Let's dive into the solution.

## Solution

Our solution to this problem is straightforward. We'll start by initializing three pointers: `prev`, `curr`, and `next`. We'll set `prev` to `NULL`, `curr` to the `head` of the input linked list, and `next` to the next node after `curr`.

We'll then iterate through the linked list, changing the direction of each node's `next` pointer. Specifically, we'll set `curr`'s `next` pointer to point to `prev`. We'll then update `prev` and `curr` to their next nodes. We'll continue doing this until `curr` reaches the end of the linked list.

Here's the Python code for our solution:

```python
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

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

        return prev
```

Let's go through this code step-by-step.

1. We start by initializing `prev` to `NULL`, `curr` to the `head` of the input linked list, and `next` to the next node after `curr`.
    

```python
prev = None
curr = head
```

1. We then iterate through the linked list, changing the direction of each node's `next` pointer.
    

```python
while curr:
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
```

Inside the loop, we set `next` to `curr`'s next node. We then set `curr`'s `next` pointer to point to `prev`. This reverses the direction of the `next` pointer for the current node. Finally, we update `prev` and `curr` to their next nodes.

1. We return `prev`, which is the new head of the reversed linked list.
    

```python
return prev
```

That's it! The linked list is now reversed.

## Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

### Time Complexity

Our solution iterates through each node in the linked list once. Since we're doing constant time operations for each node (updating pointers), the time complexity of our solution is `O(n)`, where `n` is the length of the linked list.

### Space Complexity

Our solution uses constant extra space. Therefore, the space complexity of our solution is `O(1)`.

## Conclusion

And there you have it! We've successfully tackled the Reverse Linked List problem. I hope you found this blog post helpful and informative. Happy Coding! 😎