Chương trình tìm hợp của hai danh sách liên kết đã sắp xếp trong Python

Mô tả bài toán

Cho hai danh sách liên kết đơn L1 và L2 đã sắp xếp. Trả về danh sách liên kết mới là hợp (union) của hai danh sách, cũng được sắp xếp.

Ví dụ: L1 = [10,20,30,40,50,60,70], L2 = [10,30,50,80,90] → đầu ra [10,20,30,40,50,60,70,80,90].

Giải thuật (Đệ quy hợp nhất - Merge)

1. Nếu L1 rỗng: trả về L2.
2. Nếu L2 rỗng: trả về L1.
3. Nếu L1.val < L2.val: res = L1, res.next = solve(L1.next, L2).
4. Nếu L2.val < L1.val: res = L2, res.next = solve(L2.next, L1).
5. Nếu bằng nhau: res = L1, res.next = solve(L1.next, L2.next).
6. Trả về res.

Ví dụ mã Python

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

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, L1, L2):
        if not L1:
            return L2
        if not L2:
            return L1
        if L1.val < L2.val:
            res = L1
            res.next = self.solve(L1.next, L2)
        elif L2.val < L1.val:
            res = L2
            res.next = self.solve(L2.next, L1)
        else:
            res = L1
            res.next = self.solve(L1.next, L2.next)
        return res

ob = Solution()
L1 = make_list([10,20,30,40,50,60,70])
L2 = make_list([10,30,50,80,90])
print_list(ob.solve(L1, L2))

Đầu vào

[10,20,30,40,50,60,70], [10,30,50,80,90]

Đầu ra

[10, 20, 30, 40, 50, 60, 70, 80, 90, ]