Reverse a Linked List – CA22

My Thinking and Approach

Introduction

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

At first, I thought it might be tricky because linked lists don’t allow direct indexing like arrays. But once I understood how pointers work, the solution became clear.

---

Problem Statement

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

---

My Initial Thought

Initially, I thought:

• Store elements in an array
• Reverse the array
• Rebuild the linked list

But this uses extra space and is not efficient.

So I tried to solve it directly using pointers.

---

Optimized Approach (Iterative)

I realized that:

• Each node points to the next node
• To reverse, I need to change the direction of these pointers

---

My Approach

• Use three pointers:

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

Steps

1. Initialize:

• prev = null
• curr = head

1. Traverse the list:

• Store next node → next = curr.next
• Reverse pointer → curr.next = prev
• Move prev forward
• Move curr forward

1. At the end:

• prev becomes the new head

---

Code (Java)

class Solution {
    Node reverseList(Node head) {
        Node prev = null;
        Node curr = head;

        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
}

---

Example Walkthrough

Example 1

Input:
1 → 2 → 3 → 4

Steps:

• Reverse 1 → null
• Reverse 2 → 1
• Reverse 3 → 2
• Reverse 4 → 3

Output:
4 → 3 → 2 → 1

---

Example 2

Input:
2 → 7 → 10 → 9 → 8

Output:
8 → 9 → 10 → 7 → 2

---

Complexity Analysis

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

---

Key Takeaways

• Linked lists require pointer manipulation
• Always store next node before changing links
• Iterative approach is simple and efficient

---

Conclusion

This problem helped me understand how linked lists work internally. It improved my confidence in handling pointer-based problems and showed how simple logic can reverse an entire data structure efficiently.