将一个双向循环链表追加到另一个双向循环链表的末尾（Python）

Question

所以我有一个作业要求我将一个双向循环链表附加到另一个双向循环列表的末尾。例如，我有两个双向循环链表，它们是 [0,1,2,3] 和 [10,11,12,13]。输出应为 [0,1,2,3,10,11,12,13]，我们还必须将其反转为 [13,12,11,10,3,2,1,0]

我的作业提供了两个py文件。第一个叫做“linked_list.py”。它用于创建双向循环链表。我无法修改此文件。

class Node:
    def __init__(self, x):
        self.data = x
        self.next = None
        self.pre = None

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

    def insertHead(self, x):
        self.head = Node(x)
        self.head.next = self.head
        self.head.pre = self.head

    def insert(self, y, x):
        tmp = self.head
        nodex = Node(x)
        while True:
            if tmp.data == y:
                break
            tmp = tmp.next
        nodex.next = tmp.next
        nodex.pre = tmp
        tmp.next.pre = nodex
        tmp.next = nodex

    def printForward(self):
        print("Forward :",end=" ")
        tmp = self.head
        print(tmp.data,end=" ")
        tmp = tmp.next
        while tmp!=self.head:
            print(tmp.data,end=" ")
            tmp=tmp.next
        print()

    def printBackward(self):
        print("Backward :",end=" ")
        tmp = self.head.pre
        print(tmp.data,end=" ")
        tmp = tmp.pre
        while tmp!=self.head.pre:
            print(tmp.data,end=" ")
            tmp=tmp.pre
        print()

第二个密码是“combine.py”

from linked_list import Node, DoubleLinkedList

def combine(l1, l2):
    
#This is the main part of this assignment, write a function that can combine two doubly circular linked lists. 
#There's no need to return value since we directly modify LL1 as our final result

if __name__=="__main__":
    LL1 = DoubleLinkedList()
    LL1.insertHead(0)
    LL1.insert(0, 1)
    LL1.insert(1, 2)
    LL1.insert(2, 3) #LL1 = [0,1,2,3]
    print(LL1)

    LL2 = DoubleLinkedList()
    LL2.insertHead(10)
    LL2.insert(10, 11)
    LL2.insert(11, 12)
    LL2.insert(12, 13) #LL2 = [10,11,12,13]
    print(LL2)

    combine(LL1, LL2)
    LL1.printForward()  # This function can print the combined linked list
    LL1.printBackward() # This function can reverse the 
    
    # Forward output : 0 1 2 3 10 11 12 13
    # Backward output : 13 12 11 10 3 2 1 0

一开始我想用跟普通链表追加一样的方法，后来发现循环链表的最后一个节点会指向第一个节点。然后我对整个作业感到困惑。如何使一个双向循环链表附加到另一个双向循环链表的末尾？一些详细的解释表示赞赏。提前致谢。

Answer 1

基本上，您需要在 l1 的 head 和 head.pre 之间附加完整的 l2 链。为此，我看到了两种不同的方法：

天真的那个（复杂度：O(n)）

简单地重复使用已经很好地提供给您的方法。最后，你只是要求在 l1:

末尾添加多个值

def combine(l1, l2):
    l1_tail_val = l1.head.pre.data
    l2_head = l2.head
    l1.insert(l1_tail_val, l2_head.data)
    l2_head = l2_head.next
    l1_tail_val = l2_head.data
    while l2_head != l2.head:
        l1.insert(l1_tail_val, l2_head.data)
        l1_tail_val = l2_head.data
        l2_head = l2_head.next

此方法需要遍历整个 l2，因此如果列表很大，可能需要一些时间。

编辑：这比那个更糟糕，因为为了找到插入位置，insert 方法将迭代 l1， 总是找到想要的插入位置在末尾。所以这比 O(n)

更接近 O(n^2)

高效的（复杂度：O(1)）

有了这个，你不需要迭代任何东西，你只需要连接节点，使其形成一个循环列表：

def combine(l1, l2):
    l1_tail = l1.head.pre
    l1_head = l1.head
    l2_tail = l2.head.pre
    l2_head = l2.head

    # Now just update the references
    # Then end of l2 should be connected to the head of l1 (same for the reverse relation)
    l1_head.pre = l2_tail
    l2_tail.next = l1_head
    
    # The start of l2 should be connected to the end of l1 (same for the reverse relation)
    l1_tail.next = l2_head
    l2_head.pre = l1_tail

这不依赖于任何循环或递归，因此无论列表长度如何，都会给您带来恒定的复杂性

将一个双向循环链表追加到另一个双向循环链表的末尾（Python）

Appending a doubly circular linked list to the end of another doubly circular list (Python)

python

linked-list

circular-list

doubly-linked-list