Reverse Linked List

Problem Link

206. Reverse Linked List – LeetCode

Problem Statement

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

Examples

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints

• The number of nodes in the list is in the range [0, 5000]

• -5000 <= Node.val <= 5000

Intuition

To reverse a linked list, we need to flip the direction of every next pointer so that each node points to its previous node, instead of the next.

We can use three pointers:

• prev: the node behind the current one

• curr: the current node we're processing

• next: to temporarily store curr.next before breaking the link

Approach: Iterative Reversal with Three Pointers

1. Initialize:

   • prev = null

   • curr = head

2. Traverse the list:

   • Save next = curr.next

   • Reverse the link: curr.next = prev

   • Move prev and curr one step forward

3. Once curr == null, prev is the new head of the reversed list.

Java Code

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        ListNode next = null;

        while (curr != null) {
            next = curr.next;     // store next node
            curr.next = prev;     // reverse pointer
            prev = curr;          // move prev forward
            curr = next;          // move curr forward
        }

        return prev; // new head
    }
}

Time and Space Complexity

Dry Run

Input:

head = [1,2,3]

Steps:

Result: 3 → 2 → 1 → null

Recursive Version (Optional)

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

• Time: O(n)

• Space: O(n) due to recursive stack

Conclusion

This problem is a classic example of in-place pointer manipulation in singly linked lists. Mastering this helps in many more problems such as:

• Palindrome linked list

• Reversing part of a list

• Detecting cycles