Reverse a Linked List - CA22

My Thinking and Approach

Introduction

In this problem, I was given the head of a linked list and asked to reverse the list.

After reversing, I need to return the new head of the linked list.

Problem Statement

Given the head of a linked list
Reverse the linked list
Return the new head

My Initial Thought

At first, I considered:

Storing elements in an array
Reversing the array
Rebuilding the linked list

But this approach uses extra space.

Key Observation

Instead of using extra space:

I can reverse the links between nodes
Change the direction of pointers

Optimized Approach

I decided to reverse the list using pointer manipulation.

Logic:

Keep track of previous, current, and next nodes
Reverse the link at each step

My Approach (Step-by-Step)

Initialize:

prev = None
curr = head

Traverse the list:

Store next node
Reverse current node link
Move prev and curr forward

At the end:

prev will be the new head

Code (Python)

Below is the implementation clearly separated inside a code block:

```python id="8x3q1n"
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

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

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

    return prev




---

## Example Walkthrough

### Input:



```text id="z4s8mk"
1 -> 2 -> 3 -> 4 -> 5

Steps:

Reverse links one by one
Final list becomes reversed

Output:

```text id="b0h9pe"
5 -> 4 -> 3 -> 2 -> 1




---

## Complexity Analysis

| Type             | Complexity |
| ---------------- | ---------- |
| Time Complexity  | O(n)       |
| Space Complexity | O(1)       |

---

## Key Takeaways

* Pointer manipulation is important in linked lists
* No extra space is required
* Iterative approach is efficient

---

## Conclusion

This problem helped me understand how to reverse a linked list efficiently using pointer manipulation.

---