Linked List (recursive, no tails)

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

def insert_front(head, val):
    return Node(val, head)

def insert_back(head, val):
    if head == None:
        return Node(val)
    head.nxt = insert_back(head.nxt, val)
    return head

def delete_front(head):
    if head == None:
        raise IndexError("deleting from an empty list")
    return head.nxt

def delete_back(head):
    if head == None:
        raise IndexError("deleting from an empty list")
    if head.nxt == None:
        return None
    head.nxt = delete_back(head.nxt)
    return head

def delete_one(head, val):
    if head == None:
        # no val found, so no deletion
        return None
    if head.val == val:
        return head.nxt
    head.nxt = delete_one(head.nxt, val)
    return head

def delete_all(head, val):
    if head == None:
        # no val found, so no deletion
        return None
    if head.val == val:
        return delete_all(head.nxt, val)
    head.nxt = delete_all(head.nxt, val)
    return head

def reverse_list(head):
    if head == None or head.nxt == None:
        return head
    # split list into 1 -> [2 -> 3 -> 4 -> None]. 2 is "nbeforetail"
    nbeforetail = head.nxt
    nhead = reverse_list(head.nxt)
    # once reversed nlist, we have [4 -> 3 -> 2 -> None]
    # so we link from nbeforetail to our old head and get 4 -> 3 -> 2 -> 1 -> None
    nbeforetail.nxt = head
    head.nxt = None
    return nhead

def print_list(head):
    if head == None:
        print("")
        return
    print(head.val, end=" ")
    print_list(head.nxt)

li = None
li = insert_front(li, 5)
li = insert_front(li, 20)
li = insert_front(li, 10)
li = insert_front(li, 15)
li = insert_front(li, 20)
li = insert_back(li, 2)
li = insert_back(li, 4)
li = insert_front(li, 15)
li = insert_back(li, 4)
print_list(li)
li = reverse_list(li)
print_list(li)
li = delete_all(li, 20)
li = delete_one(li, 15)
li = delete_all(li, 4)
print_list(li)