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

def create(from_list):
    first = Node(from_list[0])
    node = first
    
    for i in from_list[1:]:
        new = Node(i)
        node.next = new
        node = new

    return first

def print_list(node):
    while node is not None:
        print(node.item, end=', ')
        node = node.next
    print()

#####################################

def insert_into_sorted(node, item):
    
    if node is None:
        return Node(item)
    
    if item <= node.item:
        new = Node(item)
        new.next = node
        return new

    first = node
    while node is not None and item > node.item:
        previous = node
        node = node.next

    # previous.item < item < node.item
    new = Node(item)
    previous.next = new
    new.next = node

    return first

#####################################

def delete_one(node, item):

    # delete from beginning
    if node is not None and node.item == item:
        return node.next

    # delete from the rest
    first = node
    while node is not None:
        
        if node.item == item:  # this definitely won't be True in the first iteration
            previous.next = node.next
            return first

        previous = node
        node = node.next

    return first

#####################################

def delete_all(node, item):

    # delete from beginning
    while node is not None and node.item == item:
        node = node.next

    # delete from the rest
    first = node
    while node is not None:
        
        if node.item == item:  # this definitely won't be True in the first iteration
            previous.next = node.next
            node = previous

        previous = node
        node = node.next

    return first

#####################################

def reverse_list(node):
    reversed = None
    while node is not None:
        next = node.next
        node.next = reversed
        reversed = node
        node = next
    return reversed

# https://favtutor.com/blogs/reverse-a-linked-list-cpp
def reverse_list_recursive(node):
    if node.next is None:
        return node
    
    head = node
    rest = node.next
    rest_reversed = reverse_list_recursive(rest)
    
    rest.next = head
    head.next = None

    return rest_reversed

#####################################

def merge(node1, node2):
    if node1 is None: return node2
    if node2 is None: return node1

    if node1.item <= node2.item:
        node = node1
        node1 = node1.next
    else:
        node = node2
        node2 = node2.next
    
    node.next = None
    first = node

    while node1 is not None and node2 is not None:
        if node1.item <= node2.item:
            node.next = node1
            node1 = node1.next
        else:
            node.next = node2
            node2 = node2.next
        
        node = node.next
        node.next = None

    if node1 is not None:
        node.next = node1
    else:
        node.next = node2
    
    return first

# https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/
def merge(node1, node2):
    dummy = Node(None)

    tail = dummy
    while True:
        if node1 is None:
            tail.next = node2
            break
        if node2 is None: 
            tail.next = node1
            break

        if node1.item <= node2.item:
            tail.next = node1
            node1 = node1.next
        else:
            tail.next = node2
            node2 = node2.next
        
        tail = tail.next
    
    return dummy.next

#####################################

def split_odd_even(node):
    dummy_even = Node(None)
    dummy_odd = Node(None)
    
    tail_even = dummy_even
    tail_odd = dummy_odd

    while node is not None:
        if node.item % 2 == 0:
            tail_even.next = node
            tail_even = tail_even.next
        else:
            tail_odd.next = node
            tail_odd = tail_odd.next
        
        node = node.next

    tail_even.next = None
    tail_odd.next = None

    return dummy_even.next, dummy_odd.next

#####################################

if __name__ == '__main__':
    l = create([10, 20, 30])
    print_list(l)

    l = insert_into_sorted(l, 5)
    print_list(l)
    l = insert_into_sorted(l, 15)
    print_list(l)
    l = insert_into_sorted(l, 25)
    print_list(l)
    l = insert_into_sorted(l, 20)
    print_list(l)
    l = insert_into_sorted(l, 35)
    print_list(l)
    print()

    l = insert_into_sorted(l, 5)
    print_list(l)
    l = delete_one(l, 5)
    print_list(l)
    l = delete_one(l, 20)
    print_list(l)
    l = delete_one(l, 40)
    print_list(l)
    print()

    l = create([5, 5, 10, 15, 20, 20, 25, 35, 35])
    print_list(l)
    l = delete_all(l, 5)
    print_list(l)
    l = delete_all(l, 20)
    print_list(l)
    l = delete_all(l, 35)
    print_list(l)
    print()

    l = reverse_list(l)
    print_list(l)

    l = reverse_list_recursive(l)
    print_list(l)
    print()

    l2 = create([5, 6, 12, 16])
    m = merge(l, l2)
    print_list(m)

    e, o = split_odd_even(m)
    print_list(e)
    print_list(o)