使用递归在 python 中合并两个已排序的双向链表

Question

我正在尝试编写一种方法，使用递归（它必须是递归的）合并两个已排序的整数双向链表。该方法创建并 returns 一个新的双向链表，其中整数值按顺序排列。例如，如果 doublylinkedlist1 = [0-2-4] 和 doublylinkedlist2 = [1-3-5]，则 merge_sorted 方法将 return [0-1-2-3-4-5] .

然而，当我运行我的代码如下：

class EmptyCollection(Exception):
pass


class DoublyLinkedList:
    class Node:
        def __init__(self, data=None, next=None, prev=None):
            self.data = data
            self.next = next
            self.prev = prev

        def disconnect(self):
            self.data = None
            self.next = None
            self.prev = None

    def __init__(self):
        self.header = DoublyLinkedList.Node()
        self.trailer = DoublyLinkedList.Node()
        self.header.next = self.trailer
        self.trailer.prev = self.header
        self.size = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return (len(self) == 0)

    def first_node(self):
        if (self.is_empty()):
            raise EmptyCollection("List is empty")
        return self.header.next

    def last_node(self):
        if (self.is_empty()):
            raise EmptyCollection("List is empty")
        return self.trailer.prev

    def add_first(self, elem):
        return self.add_after(self.header, elem)

    def add_last(self, elem):
        return self.add_after(self.trailer.prev, elem)

    def add_after(self, node, elem):
        prev = node
        succ = node.next
        new_node = DoublyLinkedList.Node()
        new_node.data = elem
        new_node.prev = prev
        new_node.next = succ
        prev.next = new_node
        succ.prev = new_node
        self.size += 1
        return new_node

    def add_before(self, node, elem):
        return self.add_after(node.prev, elem)

    def delete(self, node):
        prev = node.prev
        succ = node.next
        prev.next = succ
        succ.prev = prev
        self.size -= 1
        data = node.data
        node.disconnect()
        return data

    def __iter__(self):
        if(self.is_empty()):
            return
        cursor = self.first_node()
        while(cursor is not self.trailer):
            yield cursor.data
            cursor = cursor.next

    def __str__(self):
        return '[' + '<-->'.join([str(elem) for elem in self]) + ']'

    def __repr__(self):
        return str(self)




def merge_linked_lists(srt_lnk_lst1, srt_lnk_lst2):
    return merge_sublists(srt_lnk_lst1.first_node(), srt_lnk_lst2.first_node())


def merge_sublists(a, b):
    result = DoublyLinkedList()
    if a is not None and b is not None:
        if a.data < b.data:
            result.add_last(a.data)
            return merge_sublists(a.next, b)
        else:
            result.add_last(b.data)
            return merge_sublists(a, b.next)
    elif a is not None:
        result.add_last(a.data)
        return merge_sublists(a.next, b)
    elif b is not None:
        result.add_last(b.data)
        return merge_sublists(a, b.next)
    return result



ll1 = DoublyLinkedList()
for i in range(0,10,2):
    ll1.add_last(i)
ll2 = DoublyLinkedList()
for i in range(1,10,2):
    ll2.add_last(i)
merged = merge_linked_lists(ll1, ll2)
print(merged)

我的 merge_sublists 函数出现错误，提示我无法添加 'int' 和 'Nonetype'。

有什么方法可以修改我的 merge_sublists 方法使函数正常工作吗？任何帮助表示赞赏。

Answer 1

当您到达 a 列表的末尾时，虽然对象不是 None，但您的 a.data 为 None。您需要检查数据以及列表对象。

Answer 2

问题是由放置在列表开头和结尾的虚拟列表节点引起的。尽管代码会检查空列表并跳过初始虚拟节点，但不会检查列表末尾的最终虚拟节点。因此，在跟随 a.next 和 b.next 时，它最终会遇到一个虚拟节点，该节点具有 None 作为 data 的值。当它试图将 None 与另一个节点中的数据值进行比较时发生错误。

您可以检查 a.next 和 b.next 是否在 merge_sublists 的顶部 None，但您仍然需要确保只得到一个合并列表末尾的单个虚拟节点。

最简单的方法可能是完全消除虚拟节点，并在添加新节点时检查空列表。

使用递归在 python 中合并两个已排序的双向链表

Merging two sorted Doubly Linked Lists in python using recursion

python

algorithm

recursion

doubly-linked-list