如何在不排序的情況下合并鏈表？-Python

如何創建一個簡單的函式來合并兩個鏈表，使我可以使用“合并（自我，其他）”之類的方式執行以下操作，而且我也不需要對合并的串列進行排序 - 我想合并函式只是添加，我已經包含了驅動程式代碼來提供一個想法

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()

uj5u.com熱心網友回復：

我想append是簡單合并的更好名稱。

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

uj5u.com熱心網友回復：

為了實作高效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

標籤：Python 列表 排序 合并 链表

上一篇：基數排序并行演算法C程式openmp

下一篇：如何在沒有類或ID的情況下與seleniumjava中的span互動？