# 7. Linked list
# v0.1

# 7.2 vytvorte tridu pro item z jednosmerneho linked listu
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


# 7.7 rucne vytvorte linked list obsahuji prvky: 5, 22, 1, 14, 37, 6, 12, 3
ll = Node(5, Node(22, Node(1, Node(14, Node(37, Node(6, Node(12, Node(3))))))))

print(ll.next.value)


def print_ll(ll):
    if ll is None:
        pass
    else:
        print(ll.value)
        print_ll(ll.next)


print_ll(ll)


# 7.9 napiste funkce append(ll, x) a prepend(ll, x),
# která na konec resp začátek linked listu ll vloží prvek x
def append(ll, x):
    if ll is None:
        return Node(x)

    head = ll
    while ll.next is not None:
        ll = ll.next

    ll.next = Node(x)
    return head


def prepend(ll, x):
    return Node(x, ll)


# 7.11 napiste funkci max(ll), která vrátí:
# a) největší hodnotu uloženou v linked listu,
# b) referenci\odkaz na prvek v linked listu s největší hodnotou


def max_value(ll):
    if ll is None:
        return None

    max_val = ll.value
    while ll is not None:
        if ll.value > max_val:
            max_val = ll.value
        ll = ll.next

    return max_val


def max_node(ll):
    if ll is None:
        return None

    max_n = ll
    while ll is not None:
        if ll.value > max_n.value:
            max_n = ll
        ll = ll.next

    return max_n


# 7.13 napiste funkci reverse(ll), která vrátí otočený linked list ll
# a b) rekurzivne


def reverse(ll):
    prev = None
    current = ll

    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev


def reverse_list_rec(ll):
    # Base case: empty list or last node
    if ll is None or ll.next is None:
        return ll

    # Recursively reverse the rest of the list
    new_head = reverse_list_rec(ll.next)

    # Fix the current node
    ll.next.next = ll
    ll.next = None

    return new_head


rll = reverse_list_rec(ll)
print_ll(rll)


# 7.17 napiste funkci merge(ll1, ll2),
# ktera slije dve serazene posloupnosti ulozene v ll1 a ll2
#
def merge(ll1, ll2):
    dummy = Node(0)
    tail = dummy

    while ll1 and ll2:
        if ll1.value < ll2.value:
            tail.next = ll1
            ll1 = ll1.next
        else:
            tail.next = ll2
            ll2 = ll2.next
        tail = tail.next

    if ll1:
        tail.next = ll1
    else:
        tail.next = ll2

    return dummy.next


# 7.23 vytvorte tridu LL pro reprezentaci linked listu
# a obsluznych metod
# 7.27 vlozte funkci append, prepend, max a reverse jako metody tridy LL
class LL:
    def __init__(self):
        self.head = None

    def print_ll(self):
        head = self.head
        while head is not None:
            print(head.value)
            head = head.next
    
    

    def append(self, x):
        if self.head is None:
            self.head = Node(x)
            return

        current = self.head
        while current.next:
            current = current.next

        current.next = Node(x)

    def prepend(self, x):
        self.head = Node(x, self.head)

    def max(self):
        if self.head is None:
            return None

        max_node = self.head
        current = self.head

        while current:
            if current.value > max_node.value:
                max_node = current
            current = current.next

        return max_node

    def reverse(self):
        prev = None
        current = self.head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        self.head = prev


# 7.31 a vytvorte pomoci techto funkci stejny LL jako v prikladu 7.7

ll = LL()

ll.append(5)
ll.append(22)
ll.append(1)
ll.append(14)
ll.append(37)
ll.append(6)
ll.append(12)
ll.append(3)

print("ll")
ll.print_ll()

print("ll reverse")
ll.reverse()
ll.print_ll()


# ll.head