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 node before the current node. Initially, it's nullptr (NULL).
   • curr: Points to the current node being processed. Initially, it's head.
   • next: Temporarily stores the next node in the list.

2. Iteration: We iterate through the list, reversing the links one by one. In each iteration:

   • We store the next node in next.
   • We reverse the link of curr by pointing it to prev.
   • We move prev and curr one step forward.

3. Termination: The iteration stops when curr becomes nullptr, meaning we've reached the end of the list. At this point, prev will point to the new head of the reversed list.

Explanation

The iterative approach efficiently reverses the linked list in O(n) time and O(1) space. By using three pointers, we avoid the need for extra space to store the nodes, making it highly memory-efficient. The algorithm systematically reverses the links, ensuring the correct order in the reversed list. Each node's next pointer is redirected to the previous node, effectively reversing the direction of traversal.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        ListNode* next = nullptr;

        while (curr != nullptr) {
            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 now points to the new head
    }
};

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).