Reverse a Linked List

Introduction

Linked Lists are a fundamental data structure, and one of the most important operations is reversing a linked list.

This problem helps you understand pointer manipulation, which is essential for mastering linked lists.

---

Problem Statement

Given the head of a linked list, reverse the list and return the new head.

---

Example

Input:

1 → 2 → 3 → 4 → 5 → NULL

Output:

5 → 4 → 3 → 2 → 1 → NULL

---

Intuition

In an array, reversing is easy because we can access elements by index.

But in a linked list:

• We only move forward
• So we must change the direction of links

---

Key Idea

We reverse the links by changing:

current.next → previous

---

Approach (Iterative)

We use three pointers:

• prev → previous node
• curr → current node
• next_node → store next node

---

Steps

1. Initialize:

• prev = None
• curr = head

1. Traverse the list:

• Store next node
• Reverse the link
• Move pointers forward

---

Python Implementation

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


def reverseList(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next   # store next
        curr.next = prev        # reverse link
        prev = curr             # move prev
        curr = next_node        # move curr

    return prev

---

Step-by-Step Explanation

For:

1 → 2 → 3 → 4 → 5

Iteration 1:

• Reverse 1 → NULL

Iteration 2:

• Reverse 2 → 1

Iteration 3:

• Reverse 3 → 2

Continue until:

5 → 4 → 3 → 2 → 1

---

Key Points

• No extra space needed
• Works in one pass
• Core linked list concept
• Frequently asked in interviews

---

Conclusion

Reversing a linked list is one of the most important problems in data structures. It teaches pointer manipulation and builds the foundation for more complex linked list problems.

Master this once, and many other problems become much easier.