The ListNode class represents a node in a singly linked list with attributes and methods for initialization, string representation, and equality comparison. The reverse_list function is a recursive function that reverses a singly linked list by updating the next attribute of each node to point to the previous node in the reversed list.

Cell 7

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
        
    def __str__(self): # for your debugging purposes
        return str(self.val) + '->' + str(self.next)
    
    def __eq__(self, other): # for asserts to work
            return (isinstance(other, self.__class__) 
                and self.__dict__ == other.__dict__)
        
def reverse_list(head, prev=None):
    """Recursive solution."""
    if not head:
        return prev
    nxt = head.next
    head.next = prev
    return reverse_list(nxt, head)

head = ListNode(1)
rev = ListNode(1)
assert reverse_list(head) == head

head = ListNode(1)
head.next = ListNode(2)
rev = ListNode(2)
rev.next = ListNode(1)
assert reverse_list(head) == rev

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
rev = ListNode(3)
rev.next = ListNode(2)
rev.next.next = ListNode(1)
assert reverse_list(head) == rev
print('All passed!')

class ListNode(object):
    """Represents a node in a singly linked list."""
    
    def __init__(self, x):
        """
        Initializes a ListNode with a given value.
        
        :param x: The value of the node.
        """
        self.val = x
        self.next = None
        
    def __str__(self): 
        """Returns a string representation of the node."""
        return str(self.val) + '->' + str(self.next)
    
    def __eq__(self, other): 
        """Checks if two nodes are equal."""
        return (isinstance(other, self.__class__) 
                and self.__dict__ == other.__dict__)
        
def reverse_list(head, prev=None):
    """
    Reverses a singly linked list recursively.
    
    :param head: The head of the linked list.
    :param prev: The previous node (for recursive calls).
    :return: The new head of the reversed linked list.
    """
    # Base case: if the list is empty, return the previous node (None)
    if not head:
        return prev
    # Store the next node
    nxt = head.next
    # Reverse the next pointer
    head.next = prev
    # Recursive call
    return reverse_list(nxt, head)

# Test cases
def test_reverse_list():
    # Test case 1: single node
    head = ListNode(1)
    rev = ListNode(1)
    assert reverse_list(head) == head
    
    # Test case 2: two nodes
    head = ListNode(1)
    head.next = ListNode(2)
    rev = ListNode(2)
    rev.next = ListNode(1)
    assert reverse_list(head) == rev
    
    # Test case 3: three nodes
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    rev = ListNode(3)
    rev.next = ListNode(2)
    rev.next.next = ListNode(1)
    assert reverse_list(head) == rev

test_reverse_list()
print('All passed!')

Code Breakdown

ListNode Class

The ListNode class represents a node in a singly linked list. It has the following attributes and methods:

• __init__(self, x): Initializes a new ListNode with a value x. The next attribute is set to None by default.
• __str__(self): Returns a string representation of the node for debugging purposes.
• __eq__(self, other): Implements the equality operator to compare two nodes based on their attributes.

reverse_list Function

The reverse_list function recursively reverses a singly linked list. It takes two arguments:

• head: The head of the list to be reversed.
• prev: The previous node in the reversed list (default value is None).

The function works as follows:

• If head is None, it returns prev (the new head of the reversed list).
• It stores the next node (nxt) in the original list.
• It sets the next attribute of the current node to prev (reversing the link).
• It recursively calls reverse_list with nxt as the new head and the current node as the new prev.

Test Cases

The code includes three test cases to verify the correctness of the reverse_list function. Each test case creates a linked list, reverses it using the reverse_list function, and asserts that the reversed list is correct. If all assertions pass, it prints 'All passed!'.