linkedlist.py

"""Linked list.

"""

from collections.abc import Sequence
import logging

logging.basicConfig()
logger = logging.getLogger(__name__)
logger.setLevel(level=logging.INFO)

class LinkedListNode(object):
    def __init__(self, value, next=None):
        self.next = next
        self.value = value
    def _traverse(self):
        yield self

        if self.next:
            yield from self.next._traverse()

    def __repr__(self):
        return f"LinkedListNode({self.value})"

class LinkedList(Sequence):
    def __init__(self, head=None):
        self.head = head

    def append(self, value):

        end = LinkedListNode(value)

        n = self.head

        if self.head is None:
            self.head = end
        else:
            while n.next:
                n = n.next
            n.next = end

    def _traverse(self):
        yield from self.head._traverse()

    def __getitem__(self, index):
        for i, item in enumerate(self._traverse()):
            if i == index:
                return item
        raise IndexError(f"Index {index} is out of range")

    def __len__(self):
        for count, _ in enumerate(self._traverse(), start=1):
            pass
        return count

    def __eq__(self, other):
        head1 = self.head
        head2 = other.head

        while (head1 is not None and head2 is not None):
            if head1.value != head2.value:
                logger.info(f"head1 = {head1.value}, head2 = {head2.value}")
                return False
            head1 = head1.next
            head2 = head2.next
        
        return head1 is None and head2 is None

    def __repr__(self):
        rep = [x for x in self]
        return f"LinkedList({rep})"

class Counter(object):
    value = 0

def kth_to_last(head_node, k, idx):
    if head_node is None:
        return None
    
    node = kth_to_last(head_node=head_node.next, k=k, idx=idx)
    idx.value += 1
    if idx.value == k:
        return head_node
    return node

def get_kth_to_last(linked_list, k):
    idx = Counter()
    return kth_to_last(head_node=linked_list.head, k=k, idx=idx)

def add_lists_nodes(node1, node2, carry):
    if (node1 is None and node2 is None and carry == 0):
        return None

    print(f"node1 = {node1}, node2 = {node2}")

    result = LinkedListNode(value=None)

    value = carry

    if node1 is not None:
        value += node1.value
    if node2 is not None:
        value += node2.value

    result.value = value % 10

    if node1 is not None or node2 is not None:
        new_node1 = node1.next if node1 is not None else None
        new_node2 = node2.next if node2 is not None else None
        new_value = value if value >= 10 else 0
        more = add_lists_nodes(node1=new_node1, node2=new_node2, carry=new_value)
        result.next = more
    
    return result

def add_lists(linked_list1, linked_list2):
    res = add_lists_nodes(node1=linked_list1.head, node2=linked_list2.head, carry=0)
    return LinkedList(head=res)

def reverse_and_clone(linked_list):
    reverser = reversed(linked_list)

    new_linked_list = LinkedList()
    
    for item in reverser:
        new_linked_list.append(item)

    return new_linked_list

if __name__ == "__main__":
    linked_list1 = LinkedList()
    _ = [linked_list1.append(x) for x in [1,2,3]]

    linked_list2 = LinkedList()
    _ = [linked_list2.append(x) for x in [4,5,6]]

    linked_list3 = LinkedList()
    _ = [linked_list3.append(x) for x in [1,2,3]]

    print(linked_list1)
    print(linked_list1.head)

    print(linked_list1 == linked_list2)

    print(linked_list1 == linked_list3)