Solution Explanation for Reversing a Linked List

This problem involves reversing a singly linked list. We'll explore two common approaches: iterative and recursive.

Approach 1: Iterative Reversal

This approach uses a while loop to traverse the list and reverse the links between nodes. A dummy node simplifies handling the head of the reversed list.

Algorithm:

1. Initialize: Create a dummy node. This node will eventually point to the head of the reversed list.
2. Iteration: Iterate through the original list using a curr pointer.
3. Reverse Link: In each iteration:
   • Store the next node.
   • Change the next pointer of the curr node to point to the dummy node's next.
   • Update the dummy node's next to point to curr.
   • Move curr to the next node.
4. Return: Return the next pointer of the dummy node (which is now the head of the reversed list).

Time Complexity: O(N), where N is the number of nodes in the list. We iterate through the list once.

Space Complexity: O(1). We use a constant amount of extra space.

Approach 2: Recursive Reversal

This approach uses recursion to reverse the list.

Algorithm:

1. Base Case: If the list is empty or contains only one node, return the list as is.
2. Recursive Step: Recursively reverse the rest of the list (excluding the current head node).
3. Reverse Link: After the recursive call returns the reversed tail, change the next pointer of the second node to point to the current head node.
4. Set next to null: Set the next pointer of the current head node to null.
5. Return: Return the head of the reversed list (which is the node returned by the recursive call).

Time Complexity: O(N), where N is the number of nodes in the list. Each node is visited once during the recursive calls.

Space Complexity: O(N) in the worst case due to the recursive call stack. The maximum depth of the recursion is equal to the number of nodes in the list.

Code Examples (Python)

Iterative:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        dummy = ListNode()  # Dummy node
        curr = head
        while curr:
            next = curr.next
            curr.next = dummy.next
            dummy.next = curr
            curr = next
        return dummy.next
 

Recursive:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        reversed_tail = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return reversed_tail
 

The provided code examples in other languages (Java, C++, Go, TypeScript, Rust, JavaScript, C#) follow similar logic for both iterative and recursive approaches, adapting the syntax and data structures specific to each language. The core algorithms remain consistent.