Xây dựng danh sách liên kết tổng lớn nhất từ hai danh sách đã sắp xếp trong Python

Cho hai danh sách liên kết đã sắp xếp, tạo danh sách liên kết mới có tổng giá trị lớn nhất từ đầu đến cuối. Có thể chuyển đổi giữa hai danh sách chỉ tại các nút giao (giá trị giống nhau).

Ví dụ: [6,8,35,95,115,125] và [5,8,17,37,95,105,125,135] → [6,8,17,37,95,115,125,135].

Thuật toán

• Dùng 2 con trỏ current1, current2 và previous1, previous2
• Tính tổng đoạn giữa các nút giao cho mỗi danh sách
• Chọn đoạn có tổng lớn hơn, nối nối tiếp
• Lặp đến khi hết cả hai danh sách

Ví dụ mã Python

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