Giả sử chúng ta có hai danh sách liên kết đã được sắp xếp, chúng ta phải tạo một danh sách liên kết bao gồm đường dẫn tổng lớn nhất từ nút đầu đến nút cuối. Danh sách cuối cùng có thể bao gồm các nút từ cả hai danh sách đầu vào.
Khi chúng tôi đang tạo danh sách kết quả, chúng tôi có thể chuyển sang danh sách đầu vào khác chỉ cho điểm giao nhau (hai nút có cùng giá trị trong danh sách). Chúng tôi phải giải quyết nó bằng cách sử dụng lượng không gian bổ sung liên tục.
Vì vậy, nếu đầu vào là [6,8,35,95,115,125], [5,8,17,37,95,105,125,135], thì đầu ra sẽ là [6,8,17,37,95,115,125,135]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
kết quả:=Không có
-
trước1:=a, current1:=a
-
trước2:=b, hiện tại2:=b
-
trong khi current1 không giống với None hoặc current2 không giống với None, thực hiện
-
res1:=0, res2:=0
-
trong khi current1 và current2 không null và dữ liệu của current1 không giống với dữ liệu của current2, thực hiện
-
nếu dữ liệu của current1
-
res1:=res1 + dữ liệu của current1
-
current1:=tiếp theo của current1
-
-
nếu không,
-
res2:=res2 + dữ liệu của current2
-
current2:=tiếp theo của current2
-
-
-
nếu current1 là null thì
-
trong khi current2 không null, thực hiện
-
res2:=res2 + dữ liệu của current2
-
current2:=tiếp theo của current2
-
-
-
nếu current2 là null thì
-
trong khi current1 không null, thực hiện
-
res1:=res1 + dữ liệu của current1
-
current1:=tiếp theo của current1
-
-
-
nếu trước1 giống a và trước đó 2 giống b, thì
-
kết quả:=trước1 khi (res1> res2) ngược lại trước đó2
-
-
nếu không,
-
nếu res1> res2 thì
-
tiếp theo của trước đó2:=tiếp theo của trước đó1
-
-
nếu không,
-
tiếp theo của trước đó1:=tiếp theo của trước đó2
-
-
-
trước1:=current1
-
trước2:=current2
-
nếu current1 không null thì
-
current1:=tiếp theo của current1
-
-
nếu current2 không rỗng thì
-
current2:=tiếp theo của current2
-
-
-
hiển thị nội dung của kết quả.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)
Đầu vào
[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]
Đầu ra
6 8 17 37 95 115 125 135