Remove Linked List Elements - Recursion problem

fundamental flaw

There is a fundamental flaw attempting to solve this with iteration and mutation. Try as hard as you might, remove_elements can adjust the head and next properties, but it cannot change a ListNode to None -

w = node(1)
print(w)      # ListNode { head = 1, next = None }
remove(w, 1)
print(w)      # ???

We expect to see None as the result, but this is impossible without at least one of the following -

1. the function call must change
2. the data structure for ListNode must change

Presuming you want to maintain the shape of ListNode, we must adjust the function call to -

w = node(1)
print(w)
w = remove_elements(w, 1)   # <- reassign with result of call
print(w)

Now using the return value of remove_elements we can catch the scenario where ListNode is demoted to a plain None. Using your first example -

p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))

print(to_str(p))
p = remove_elements(p, 6)   # <- reassign p
print(to_str(p))

6->1->2->6->3->4->5->6->∅
1->2->3->4->5->∅

And your second example -

q = node(1, node(1))

print(to_str(q))
q = remove_elements(q, 1)    # <- reassign q
print(to_str(q))

1->1->∅
∅

Here is the implementation of a mutable singly linked list -

class node:
  def __init__(self, head, next = None):
    self.head = head
    self.next = next

def remove_elements(t, val):
  # load stack
  s = []
  while t:
    if t.head != val:
      s.append(t)
    t = t.next

  # unload stack
  r = None
  while s:
    q = s.pop()
    q.next = r
    r = q
  
  # return
  return r

def to_str(t):
  r = ""
  while t:
    r = r + str(t.head) + "->"
    t = t.next
  return r + "∅"

know your origins

This question is tagged with recursion and rightfully so. The linked list is a recursive data structure and choosing a recursive program to process it harmonizes the structure of our program with the structure of our data. However, recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects. Instead of destroying existing values, a new value is created -

1. If the input list, t, is empty, the base case has been reached. Return the empty list
2. (inductive) the input is not empty; it has at least one element. If the first element, t.head, matches the value to remove, val, return the result of the sub-problem, t.next
3. (inductive) the input is not empty and the first element does not match the value to remove. Construct a new list node of t.head and the result of the sub-problem t.next -

def remove_elements(t, val):
  if not t:
    return None                                           # 1
  elif t.head == val:
    return remove_elements(t.next, val)                   # 2
  else:
    return ListNode(t.head, remove_elements(t.next, val)) # 3

For your first example -

p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))

print(to_str(p))
print(to_str(remove_elements(p, 6)))

6->1->2->6->3->4->5->6->∅
1->2->3->4->5->∅

Using your other example -

q = node(1, node(1))

print(to_str(q))
print(to_str(remove_elements(q, 1)))

1->1->∅
∅

Here's the implementation of an immutable (persistent) singly linked list -

class node:
  def __init__(self, head, next = None):
    self.head = head
    self.next = next

def remove_elements(t, val):
  if not t:
    return None
  elif t.head == val:
    return remove_elements(t.next, val)
  else:
    return node(t.head, remove_elements(t.next, val))

def to_str(t):
  if not t:
    return "∅"
  else:
    return str(t.head) + "->" + to_str(t.next)

attention

The immutable implementation does not mutate existing values. That means new values are created -

p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))
q = remove_elements(p, 6)

When we write q = remove_elements(p, 6), a new list is created and stored to q and p is unchanged -

print(to_str(q))
print(to_str(p))

1->2->3->4->5->∅                # q is a new list
6->1->2->6->3->4->5->6->∅       # p is unchanged

disentangle

Notice each implementation of remove_elements is a plain function and disentangled from a class. If your program requires a class-based solution, it becomes a simple wrapper around our plain function -

class solution:
  class remove_elements(self, t, val):
    return remove_elements(t, val)

If you're going to use recursion, you could use it to relink the elements as you go. This would only require the removeElements function itself to recurse:

def removeElements(self,head,val):
    if not head: return None                           # end of list
    if head.val == val:
        head = self.removeElements(head.next,val)      # remove head
    else:
        head.next = self.removeElements(head.next,val) # keep head 
    return head

Here are the issues in your code:

• When you call checkHead recursively, you don't capture the value it returns, and so the recursive call is useless. The only utility it has, is in what it returns. So just like you already do correctly in removeElements, you should also here assign the returned value to head:

  head = self.checkhead(head,val)
  

• elif head.val is wrong. It should be elif head.val == val. It is a pity you need this elif at all. If you would make the if condition (above it) test head instead of head.next, you wouldn't need the elif case at all.

• The while curr loop does not treat well the case where the searched value occurs twice in a row. In that case you also move cur to cur.next, and the next iteration will not look at cur.val, but at cur.next.val. So the value at cur is never inspected. So... you should do cur = cur.next in an else block.

• The final return is wrong. You should not return None, since the while cur loop could have kept some nodes in the list. So return head.

With these changes it is also not really necessary to have two if not head checks: both can now be omitted.

Here is the corrected code:

class Solution:
    def checkHead(self, head, val):
        # Check that head is not None, instead of checking head.next
        if head and head.val == val:
            # Should use the value returned by recursive call
            head = self.checkHead(head.next, val)
        return head

    def removeElements(self, head: ListNode, val: int) -> ListNode:
        head = self.checkHead(head, val)
        curr = head 
        while curr and curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
            else: # Only move to next when no match
                curr = curr.next
        return head  # Should return head, not None

This will work. Still, it is a bit strange to see a mix of recursive and iterative code, which is also the reason why you needed a separate method besides removeElements. You can actually do all with recursion:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if head:
            if head.val == val:
                return self.removeElements(head.next, val)
            else:
                head.next = self.removeElements(head.next, val)
                return head