Reverse a linked list

Given the head of a linked list, the task is to reverse this list and return the reversed head.

Examples:

Input: head: 1 -> 2 -> 3 -> 4 -> NULL
Output: head: 4 -> 3 -> 2 -> 1 -> NULL
Explanation:

Input: head: 2 -> 7 -> 10 -> 9 -> 8 -> NULL
Output: head: 8 -> 9 -> 10 -> 7 -> 2 -> NULL
Explanation:

Input: head: 2 -> NULL
Output: 2 -> NULL
Explanation:

Constraints:
1 <= number of nodes, data of nodes <= 10⁵

Approach 01:

class Solution {
public:
    Node* reverseList(Node* head) {
        Node* currentNode = head;
        Node* previousNode = nullptr;

        while (currentNode != nullptr) {
            Node* nextNode = currentNode->next; // Temporarily store the next node
            currentNode->next = previousNode;       // Reverse the current node's pointer
            previousNode = currentNode;             // Move previousNode to this node
            currentNode = nextNode;                 // Move to the next node
        }
        return previousNode; // New head of the reversed list
    }
};

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        currentNode = head
        previousNode = None

        while currentNode:
            nextNode = currentNode.next  # Temporarily store the next node
            currentNode.next = previousNode  # Reverse the current node's pointer
            previousNode = currentNode  # Move previousNode to this node
            currentNode = nextNode  # Move to the next node
        return previousNode  # New head of the reversed list

Time Complexity:

• Traversal of the Linked List:

  The algorithm traverses the entire linked list exactly once, processing each node during the iteration. If the list contains \( n \) nodes, the traversal takes \( O(n) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity:

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for pointers currentNode, previousNode, and nextNode. Thus, the auxiliary space is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).