如何合并链表而不排序？- Python

Question

我怎样才能创建一个简单的函数来合并两个链表，这样我就可以像' merge (self，other)‘这样做，而且我不需要我的合并列表进行排序-我希望merge函数只是简单地相加，并且我已经包含了驱动程序代码来给出一个概念

ls = [2,3,4,5]
ls2 = [42, 17]
ls.merge(ls2) # should change ls to [2,3,4,5,42,17]
ls2.head.data = 24  # should change ls2 to [24,17] and ls to [2,3,4,5,24,17]
    
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def merge_sorted(self, llist):
    
        p = self.head 
        q = llist.head
        s = None
    
        if not p:
            return q
        if not q:
            return p

        if p and q:
            if p.data <= q.data:
                s = p 
                p = s.next
            else:
                s = q
                q = s.next
            new_head = s 
        while p and q:
            if p.data <= q.data:
                s.next = p 
                s = p 
                p = s.next
            else:
                s.next = q
                s = q
                q = s.next
        if not p:
            s.next = q 
        if not q:
            s.next = p 
        return new_head

llist_1 = LinkedList()
llist_2 = LinkedList()

llist_1.append(1)
llist_1.append(5)
llist_1.append(7)
llist_1.append(9)
llist_1.append(10)

llist_2.append(2)
llist_2.append(3)
llist_2.append(4)
llist_2.append(6)
llist_2.append(8)

llist_1.merge_sorted(llist_2)
llist_1.print_list()

Answer 1

我想append是simple merge的一个更好的名字。

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None # If we don't store tail, `append` would be O(n)

    def append(self, other): # `other` is also a `LinkedList`
        if self.head:
            self.tail.next = other.head
            self.tail = other.tail
        else:
            self.head = other.head
            self.tail = other.tail

Answer 2

要实现高效的append和merge实现，需要将tail属性添加到链表实现中

我会投票反对print_list方法，因为打印不应该由这样的类管理。相反，提供一个方法，该方法将提供列表的字符串表示，并让主程序决定是否打印该列表。

下面是它的工作原理：

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


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # <-- add this to have an efficient append/merge method

    def append(self, data):
        node = Node(data)
        if not self.head:  # When this list is empty
            self.head = node
        else:
            self.tail.next = node
        self.tail = node

    def merge(self, llist):
        if not self.head:  # When this list is empty
            self.head = llist.head
        else:
            self.tail.next = llist.head
        self.tail == llist.tail

    def __iter__(self):  # To facilitate any need to iterate through the list
        node = self.head
        while node:
            yield node.data
            node = node.next

    def __str__(self):  # Don't make a print method; instead provide a string
        return "->".join(map(str, self))  # This calls self.__iter__()


llist_1 = LinkedList()
llist_2 = LinkedList()

llist_1.append(1)
llist_1.append(5)
llist_1.append(7)
llist_1.append(9)
llist_1.append(10)

llist_2.append(2)
llist_2.append(3)
llist_2.append(4)
llist_2.append(6)
llist_2.append(8)

llist_1.merge(llist_2)
print(llist_1)  # Only call `print` here