LinkedList - patch - ariadna/AlgoritmStructure_Ari

LinkedList
177 строк4 KB
ariadna
update LinkedList cycle
29 мар 2025, 15:06
29 мар 2025, 15:068910bc5
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


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

    def build(self, data_list):
        self.head = None
        tail = None
        for data in data_list:
            new_Node = Node(data)
            if self.head is None:
                self.head = new_Node
                tail = new_Node
            else:
                tail.next = new_Node
                tail = new_Node

    def len(self):

        count = 0
        curr = self.head
        while curr:
            count += 1
            curr = curr.next
        return count

    def get_at(self, index):

        if index < 0 or index >= self.len():
            print("Index out of range")
            return None
        curr = self.head
        for i in range(index):
            curr = curr.next
        return curr.data

    def set_at(self, index, data):

        if index < 0 or index >= self.len():
            print("Index out of range")
            return None
        curr = self.head
        for i in range(index):
            curr = curr.next
        curr.data = data

    def delete_at(self, index):

        if index < 0 or index >= self.len():
            print("Index out of range")
            return None
        if index == 0:
            self.delete_first()
            return
        curr = self.head
        prev = None
        for i in range(index):
            prev = curr
            curr = curr.next
        prev.next = curr.next

    def delete_first(self):

        if self.head is None:
            return
        self.head = self.head.next

    def delete_last(self):
        if self.head is None:
            return
        if self.head.next is None:
            self.head = None
            return
        curr = self.head
        while curr.next.next:
            curr = curr.next
        curr.next = None

    def insert_at(self, index, data):

        if index < 0 or index > self.len():
            print("Index out of range")
            return None
        if index == 0:
            self.insert_first(data)
            return
        curr = self.head
        prev = None
        for i in range(index):
            prev = curr
            curr = curr.next
        new_Node = Node(data)
        new_Node.next = curr
        prev.next = new_Node

    def insert_first(self, data):

        new_Node = Node(data)
        new_Node.next = self.head
        self.head = new_Node

    def insert_last(self, data): 
        new_Node = Node(data)
        if self.head is None:
            self.head =new_Node
        else:
            last = self.head
            while last.next:
                last =last.next
            last.next = new_Node

    def search(self,key):
        current = self.head
        while current is not None:
            if current.data == key:
                return True
            current = current.next
        return False

#Задание Найти k-й элемент с конца связаного списка.
    def find_kth_f_end(self, k):
        if not self.head or k<=0:
            return None
        
        slow = self.head
        fast = self.head

        for i in range(k):
            if not fast:
                return None
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next
        return slow.data

#Задание Найти середину связаного списка за одну проходку
    def seredin(self):
        slow = self.head
        fast = self.head

        
        while fast  and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        return slow.data

# Задание поиск длины цикла 
    def find_cycle_length(head):
    
        slow = head
        fast = head

        while fast and fast.next:
            slow =slow.next
            fast =fast.next.next
            if slow == fast:
                break 

        if not fast or not fast.next:
            return 0


        cycle_leng =1
        current=slow.next 
        while current != slow: 
            cycle_length +=1
            current = current.next

        return cycle_leng