資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學構建一個最大和連結串列，該連結串列由兩個包含一些公共節點的有序連結串列構成 (Python)
假設我們有兩個有序連結串列，我們需要建立一個連結串列，該連結串列包含從起始節點到結束節點的最大和路徑。最終的連結串列可能包含來自兩個輸入連結串列的節點。
在建立結果連結串列時，我們只可以在交點（兩個連結串列中具有相同值的節點）處切換到另一個輸入連結串列。我們必須使用恆定的額外空間來解決這個問題。
因此，如果輸入類似於 [6,8,35,95,115,125]，[5,8,17,37,95,105,125,135]，則輸出將為 [6,8,17,37,95,115,125,135]
為了解決這個問題，我們將遵循以下步驟：
result := None
previous1 := a, current1 := a
previous2 := b, current2 := b
當 current1 不為 None 或 current2 不為 None 時，執行以下操作：
res1 := 0, res2 := 0
當 current1 和 current2 不為 null 且 current1 的資料與 current2 的資料不相同時，執行以下操作：
如果 current1 的資料 < current2 的資料，則：
res1 := res1 + current1 的資料
current1 := current1 的下一個節點
否則：
res2 := res2 + current2 的資料
current2 := current2 的下一個節點
如果 current1 為 null，則：
當 current2 不為 null 時，執行以下操作：
res2 := res2 + current2 的資料
current2 := current2 的下一個節點
如果 current2 為 null，則：
當 current1 不為 null 時，執行以下操作：
res1 := res1 + current1 的資料
current1 := current1 的下一個節點
如果 previous1 等於 a 且 previous2 等於 b，則：
result := 如果 (res1 > res2) 則為 previous1，否則為 previous2
否則：
如果 res1 > res2，則：
previous2 的下一個節點 := previous1 的下一個節點
否則：
previous1 的下一個節點 := previous2 的下一個節點
previous1 := current1
previous2 := current2
如果 current1 不為 null，則：
current1 := current1 的下一個節點
如果 current2 不為 null，則：
current2 := current2 的下一個節點
顯示 result 的內容。
示例
讓我們來看下面的實現以獲得更好的理解：
class LinkedList(object): def __init__(self, data_set = []): self.head = None if len(data_set) > 0: for item in data_set: self.insert_node(item) class ListNode(object): def __init__(self, d): self.data = d self.next = None def insert_node(self, new_data): new_node = self.ListNode(new_data) new_node.next = self.head self.head = new_node def find_max_sum_list(self, a, b): result = None previous1 = a current1 = a previous2 = b current2 = b while current1 != None or current2 != None: res1 = 0 res2 = 0 while current1 != None and current2 != None and current1.data != current2.data: if current1.data < current2.data: res1 += current1.data current1 = current1.next else: res2 += current2.data current2 = current2.next if current1 == None: while current2 != None: res2 += current2.data current2 = current2.next if current2 == None: while current1 != None: res1 += current1.data current1 = current1.next if previous1 == a and previous2 == b: result = previous1 if (res1 > res2) else previous2 else: if res1 > res2: previous2.next = previous1.next else: previous1.next = previous2.next previous1 = current1 previous2 = current2 if current1 != None: current1 = current1.next if current2 != None: current2 = current2.next while result != None: print(result.data, end = ' ') result = result.next my_list1 = LinkedList([125,115,95,35,8,6]) my_list2 = LinkedList([135,125,105,95,37,17,8,5]) my_list1.find_max_sum_list(my_list1.head, my_list2.head)
輸入
[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]
輸出
6 8 17 37 95 115 125 135
126 次瀏覽
