Reverse Linked List

class Solution {
public:
    ListNode* reverse(ListNode* current) {
        if (current == nullptr || current->next == nullptr) {
            return current;
        }
        ListNode* reversedHead = reverse(current->next);
        current->next->next = current;
        current->next = nullptr;
        return reversedHead;
    }
};

The provided C++ code defines a solution to reverse a linked list using recursion. The function reverse takes a pointer to a ListNode as its parameter, which represents the current node of the linked list. This function implements the following logic:

1. Base case: If the current node is nullptr or the next node of current is nullptr, the function returns the current node. This handles the cases where the list is empty or has just one node.
2. Recursive step: The function recurses by calling reverse with the next node in the list.
3. Reversal logic: Upon return from the recursive call, it sets the next pointer of the next node to point back to the current node, effectively reversing the direction of the link.
4. Detachment: It then detaches the current node's next pointer by setting it to nullptr to ensure the previous start of the list now becomes the end.
5. Completion: Once the entire list has been processed, reversedHead (which now points to the new head of the reversed list) is returned.

This recursive approach elegantly handles the reversal of a linked list by repositioning the links between nodes from the recursive call stack, ensuring that each node points to its predecessor, thus reversing the linked list.

class Solution {
    public ListNode reverseLinkedList(ListNode start) {
        if (start == null || start.next == null) {
            return start;
        }
        ListNode newHead = reverseLinkedList(start.next);
        start.next.next = start;
        start.next = null;
        return newHead;
    }
}

This Java solution addresses the problem of reversing a linked list. The method reverseLinkedList employs a recursive approach to invert the order of nodes in the list. Initially, the method checks if the start node is null or a single node by evaluating if start.next is null, in which case it directly returns the start as reversing a single element or an empty list doesn't alter the list.

During each recursive call:

• The function dives to the deepest node in the list using reverseLinkedList(start.next).
• It sets the next node's next reference to point back to the current start node effectively reversing the link.
• It then severs the original link by setting start.next to null.

Finally, the new head of the reversed list is returned upward through the recursion stack, culminating in the original call returning the new head of the completely reversed list. This tail-end method leverages the call stack to reverse the pointers efficiently without the need for auxiliary data structures.

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

The Python solution provided implements the reversal of a linked list using recursion. This method focuses on handling each node in the linked list, flipping its direction, and ensuring the list remains connected appropriately.

• The function reverseLinkedList is a recursive function. It accepts a head which is the starting node of the linked list.
• Check whether the head is null or it's the last node in the list (head.next is null). If true, return the head as it represents either an empty list or the last node which will become the new head of the reversed list.
• Recursively call reverseLinkedList with the next node of the current head. This step continues until the base condition is met (reaching the end of the list).
• Once reaching the end, reassign the next node's pointer, thus reversing the link. Specifically, head.next.next = head sets the next node's next pointer to the current node, effectively reversing the link.
• Set head.next to None to break the original link and avoid cycles in the list.
• Return newHead, the new head of the reversed list, which is obtained from the recursive calls reaching the base case.

This approach effectively reverses the linked list in-place without requiring additional data structures, relying on the call stack to handle the reversal as the recursion unwinds.