Reverse Linked List easy

Problem Statement

Reverse a singly linked list.

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: []

Steps

1. Iterative Approach: We'll use three pointers: prev, curr, and next.

   • prev: Points to the previously reversed node (initially null).
   • curr: Points to the current node being processed (initially the head).
   • next: Stores the next node to be processed.

2. Iteration: We iterate through the list, reversing the links as we go. In each iteration:

   • We store the curr.next in next to avoid losing the reference to the next node.
   • We reverse the link of curr by setting curr.next to prev.
   • We move prev and curr one step forward (prev = curr, curr = next).

3. Termination: The iteration continues until curr becomes null (we reach the end of the list).

4. Return: The prev pointer will now point to the new head of the reversed list.

Explanation

The iterative approach efficiently reverses the linked list in-place without using extra space. By cleverly manipulating the pointers, we change the direction of the links connecting the nodes. The key is understanding how the prev, curr, and next pointers work together to smoothly reverse the links one node at a time. The process essentially "unlinks" a node from its successor and links it to its predecessor until the entire list is reversed.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;

        while (curr != null) {
            next = curr.next; // Store the next node
            curr.next = prev; // Reverse the link
            prev = curr;      // Move prev forward
            curr = next;      // Move curr forward
        }

        return prev; // prev is now the head of the reversed list
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use a constant amount of extra space for the pointers (prev, curr, next).