CODEWITHSUNDEEP
pythonlinked-list
Tree Garen
Tree Garen

Reputation: 205

Linked list recursive delete operation: How do I change the head?

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def rec_delete(head, val, prev=None):
    if(head == None):
        return False
    if(head.val == val):
        if(prev == None):
            head = head.next
        else:
            prev.next = head.next
        return True
    
    return rec_delete(head.next, val, head)


head = Node(1, Node(2, Node(3, Node(4))))
rec_delete(head, 1)
rec_delete(head, 2)
rec_delete(head, 3)
rec_delete(head, 4)

Given a linked list 1 -> 2 -> 3 -> 4 I want to remove all the elements one by one but unsure how to assign a new head in python. The issue with my current code is since head goes through a function I cannot reassign the head. I want head to be None after all the operations.

Upvotes: 0

Views: 92

Answers (1)

Samwise
Samwise

Reputation: 71522

Your delete function needs to return the head of the list after val has been deleted. This not only makes the implementation of the delete much simpler (the base case is the one where the head is itself being deleted), it is necessary for the caller to be able to handle the case where the head is deleted.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
        
    def __repr__(self):
        """val1 -> val2 -> val3 ..."""
        return f"{self.val}" + (f" -> {self.next}" if self.next else "")


def delete(head, val):
    """Delete val from list with given head, returning head of the modified list."""
    if head.val == val:
        # Deleting head, so the new head is head.next.
        return head.next
    # Head remains head, but we still need to delete val from head.next.
    head.next = delete(head.next, val)
    return head


head = Node(1, Node(2, Node(3, Node(4))))
print(head)  # 1 -> 2 -> 3 -> 4
head = delete(head, 1)
head = delete(head, 2)
print(head)  # 3 -> 4
head = delete(head, 3)
head = delete(head, 4)
print(head)  # None

Upvotes: 1

Related Questions