Reverse Linked List

Google Interview Question

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

Input: 1 → 2 → 3 → 4 → 5
Output: 5 → 4 → 3 → 2 → 1

Input: 1 → 2
Output: 2 → 1

---

Step 1: Clarify Requirements

• Can the list be empty?

• Can the list have only one node?

• Should we return a new list or reverse in-place?

---

Step 2: Discuss Approaches

🟡 Approach 1: Brute Force

• Logic:

  • Traverse the list and store values in an array

  • Reverse the array

  • Now, build a new linked list using that array

• Time Complexity:

  • O(n)

  • We need to go through the entire list

• Space Complexity:

  • O(n)

  • We are using an array
    

🟢 Approach 2: In-Place Reversal (Optimal)

• Logic:

  • Use 3 pointers:

    • prev, curr, next

  • At each step:

    • Save curr.next as the next node

    • Now, set curr.next = prev

    • We have now reversed the current node

    • Now, move prev and curr one node ahead

    • Repeat the same steps

  • At the end, the entire list will be reversed

• Time Complexity:

  • O(n)

  • We need to go through the entire list

• Space Complexity:

  • O(1)

  • We are doing reversal in-place

---

Step 3: Write Code (Optimal)

---

Step 4: Answer Follow-Ups

• What if the list is empty or has one node?

  • It’s already reversed.

  • Just return the head as is.

• What if we need to reverse only part of the list?

  • Use a counter to stop at given bounds.

  • Reverse nodes only between those indices.

• What if the list is doubly linked?

  • In this case, we can’t just reverse the next pointer.

  • We need to reverse both next and prev pointers.

  • Still possible in O(n) time and O(1) space.

---

🤝 Join Me on LinkedIn

• 40K+ strong community

• Join Here: LinkedIn URL

---

👨‍💻 Need Interview Practice?

• Book a 1:1 with me

• Book Here: Booking URL