Beispiel für eine Python-Codelösung

`python`



from chap2_function import* 

def dll_from_node(node): 
  
    dll = DoublyLinkedList()

    while(node is not None): 
        dll.append(node.data) 
        last = node 
        node = node.next

    return dll

class Result:
    
    #Konstrukteur
    def __init__(self, tail, size):
        self.tail = tail
        self.size = size 

def findIntersection(list1,list2):

    if list1 == None or list2 == None:
        return None

    result1 = getTailAndSize(list1)
    result2 = getTailAndSize(list2)

    if result1.tail != result2.tail:
        return None
    
    shorter = list1 if result1.size < result2.size else list2
    longer = list2 if result1.size < result2.size else list1

    longer = getKthNode(longer,abs(result1.size-result2.size))

    while shorter.data != longer.data:
        shorter = shorter.next
        longer = longer.next

    return longer

def getTailAndSize(list_node):

    if list_node == None:
        return None

    size = 1
    current = list_node

    while current.next:
        size = size + 1
        current = current.next
    
    return Result(current,size)

def getKthNode(head_node,k):
    
    current = head_node

    while k>0 and current:
        current = current.next
        k = k - 1

    return current

dll_1 = DoublyLinkedList() 

# DLL: None -> 3(Kopf) -> 1 -> 5 -> 9 -> 7 -> 2 ->1(letzte) -> None 
dll_1.append(3)  
dll_1.append(1) 
dll_1.append(5) 
dll_1.append(9) 
dll_1.append(7)  
dll_1.append(2) 
dll_1.append(1) 

dll_1.printList(dll_1.head) 

dll_2 = DoublyLinkedList() 

# DLL: None -> 4(Kopf) -> 6 -> 7 -> 2 ->1(letzte) -> None 
dll_2.append(4)  
dll_2.append(6) 
dll_2.insertNode(dll_2.head.next,dll_1.head.next.next.next.next)

dll_2.printList(dll_2.head) 

result_dll = dll_from_node(findIntersection(dll_1.head,dll_2.head))
result_dll.printList(result_dll.head)

Python-Funktionen (Knotenklasse, bidirektionale Listenklasse)

`chap2_function.py`


#Knotenklasse
class Node: 
  
    #Konstrukteur
    def __init__(self, data): 
        self.data = data 
        self.next = None
        self.prev = None
  
#Bidirektionale Listenklasse
class DoublyLinkedList: 
  
    #Konstrukteur
    def __init__(self): 
        self.head = None
  
    #Knoten vom ersten Knoten einfügen
    def push(self, new_data): 
  
        #Knotengenerierung
        new_node = Node(new_data) 
  
        #Machen Sie den nächsten Knoten des neuen Knotens zu dem, der ursprünglich der Hauptknoten war
        new_node.next = self.head 
  
        #Obwohl es sich in erster Linie um einen Kopfknoten handelte, wird der vorherige Knoten in einen neuen Knoten geändert
        if self.head is not None: 
            self.head.prev = new_node 
  
        #Machen Sie den neuen Knoten zu einem Kopfknoten
        self.head = new_node 
  
    #Einfügen eines Knotens an einem Zwischenpunkt
    def insert(self, prev_node, new_data): 
  
        # prev_Geben Sie an, ob ein Knoten nach dem vom Knoten angegebenen Knoten eingefügt werden soll
        #Wenn Keine, beenden Sie die Funktion
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
  
        #Knotengenerierung
        new_node = Node(new_data) 
  
        #Zurück zum nächsten Knoten des neuen Knotens_Machen Sie es zum nächsten Knoten des vom Knoten angegebenen Knotens
        new_node.next = prev_node.next
  
        # prev_Macht den nächsten Knoten des vom Knoten angegebenen Knotens zu einem neuen Knoten
        prev_node.next = new_node 
  
        #Zurück zum vorherigen Knoten des neuen Knotens_Machen Sie es zum Knoten, der vom Knoten angegeben wird
        new_node.prev = prev_node 
  
        #Zurück zum nächsten Knoten des neuen Knotens_Ich habe es zum nächsten Knoten des in Knoten angegebenen Knotens gemacht, aber der vorherige Knoten dieses Knotens wird auch zu einem neuen Knoten gemacht
        if new_node.next is not None: 
            new_node.next.prev = new_node 

    def insertNode(self, prev_node, new_node): 
  
        # prev_Geben Sie an, ob ein Knoten nach dem vom Knoten angegebenen Knoten eingefügt werden soll
        #Wenn Keine, beenden Sie die Funktion
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
        
        if new_node is None: 
            print("the given new node cannot be NULL")
            return 
  
        # prev_Macht den nächsten Knoten des vom Knoten angegebenen Knotens zu einem neuen Knoten
        prev_node.next = new_node 
  
        #Zurück zum vorherigen Knoten des neuen Knotens_Machen Sie es zum Knoten, der vom Knoten angegeben wird
        new_node.prev = prev_node 
  
  
    #Knoten vom letzten Knoten einfügen
    def append(self, new_data): 
  
        #Knotengenerierung
        new_node = Node(new_data) 
  
        #Keine Definition des nächsten Knotens des neuen Knotens
        new_node.next = None
  
        #Wenn kein Kopfknoten festgelegt ist (leere Liste), legen Sie einen neuen Knoten als Kopfknoten fest
        if self.head is None: 
            new_node.prev = None
            self.head = new_node 
            return 
  
        #Stellen Sie den endgültigen Knoten ein (Vorwärtsscannen)
        last = self.head 
        while(last.next is not None): 
            last = last.next
  
        #Legen Sie einen neuen Knoten als letzten Knoten fest
        last.next = new_node 
  
        # 7.Machen Sie den vorherigen Knoten des neuen Knotens zum letzten Knoten überhaupt
        new_node.prev = last 
  
        return
  
    def delete(self,del_node):

        if self.head == None or del_node == None: 
            return 

        if self.head == del_node: 
            self.head = del_node.next

        if del_node.next != None: 
            del_node.next.prev = del_node.prev 

        if del_node.prev != None: 
            del_node.prev.next = del_node.next

    # This function prints contents of linked list 
    # starting from the given node 
    def printList(self, node): 

        last = None
  
        print("Bidirektionale Liste: \n") 

        print("Vorwärtsscannen")
        while(node is not None): 
            print(node.data,end="") 
            last = node 
            node = node.next
            if node:
                print(" -> ",end="")
            else:
                print("\n")
  
        print("Reverse Scannen")
        while(last is not None): 
            print(last.data,end="")
            last = last.prev 
            if last:
                print(" -> ",end="")
            else:
                print("\n")
  
if __name__ == '__main__':
    #Generieren Sie eine leere bidirektionale Liste
    # DLL: None
    dll = DoublyLinkedList() 
    # DLL: None -> 6(Kopf/letzte) -> None
    dll.append(6) 
    # DLL: None -> 7(Kopf) -> 6(letzte) -> None 
    dll.push(7) 
    # DLL: None -> 1(Kopf) -> 7 -> 6(letzte) -> None 
    dll.push(1) 
    # DLL: None -> 1(Kopf) -> 7 -> 6 -> 4(letzte) -> None 
    dll.append(4) 
    # DLL: None -> 1(Kopf) -> 7 -> 8 -> 6 -> 4(letzte) -> None 
    dll.insert(dll.head.next, 8) 
    # DLL: None -> 1(Kopf) -> 8 -> 6 -> 4(letzte) -> None 
    dll.delete(dll.head.next) 

    dll.printList(dll.head)

Verweise

[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion) [2] GeeksforGeeks: Delete a node in a Doubly Linked List