🔁 Reverse a Linked List – Python (Step-by-Step)

Hi All,

Today I solved a fundamental problem in Data Structures: Reverse a Linked List.

---

📌 Problem Statement

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

---

🔍 Example

Input:

1 -> 2 -> 3 -> 4 -> 5

Output:

5 -> 4 -> 3 -> 2 -> 1

---

💡 Approach

🔹 Iterative Method (Optimal)

👉 We reverse the links one by one using pointers.

---

🧠 Step-by-Step Logic

We use three pointers:

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

---

Steps:

1. Initialize:

   • prev = None
   • curr = head

2. Traverse the list:

   • Store next node
   • Reverse link
   • Move pointers forward

---

💻 Python Code

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


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

---

🔍 Dry Run

For:

1 -> 2 -> 3

Steps:

• Reverse 1 → None
• Reverse 2 → 1
• Reverse 3 → 2 → 1

Final:

3 -> 2 -> 1

---

🖥️ Sample Output

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

---

⚡ Complexity Analysis

• Time Complexity: O(n) ✅
• Space Complexity: O(1) ✅

---

🧠 Alternative Method (Recursive)

def reverseList(head):
    if not head or not head.next:
        return head

    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None

    return new_head

---

🧠 Why this is important?

• Core linked list concept
• Tests pointer manipulation
• Frequently asked in interviews

---

✅ Conclusion

This problem helped me understand:

• Pointer handling
• Linked list traversal
• In-place reversal

🚀 Must-know problem for coding interviews!

---