Problem: Reverse a Linked List

Problem Statement

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

Approach: In-Place Reversal

We use three pointers to track the previous, current, and next nodes.

1. Initialize: prev = null, curr = head.
2. Iterate:
   • Save the next node: nextTemp = curr.next.
   • Reverse the link: curr.next = prev.
   • Advance pointers: prev = curr, curr = nextTemp.
3. Return: prev becomes the new head.

Java Implementation

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode nextTemp = curr.next; // Store next
        curr.next = prev;              // Reverse
        prev = curr;                   // Move prev forward
        curr = nextTemp;               // Move curr forward
    }
    
    return prev;
}

Dry Run

Input: 1 -> 2 -> 3 -> null

Complexity Analysis

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