Chương trình tìm giao của hai danh sách liên kết 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. Tạo danh sách liên kết mới là giao (intersection) của hai danh sách, cũng được sắp xếp.

Ví dụ: L1 = [2,4,8], L2 = [3,4,8,10] → đầu ra [4,8].

Giải thuật (Hai con trỏ - Two Pointers)

1. Tạo nút giả head, con trỏ cur = head.
2. Khi cả l1 và l2 không rỗng:
   • Nếu l1.val < l2.val: l1 = l1.next.
   • Nếu l2.val < l1.val: l2 = l2.next.
   • Nếu bằng nhau: tạo nút mới với giá trị đó, nối vào cur, tiến cả hai con trỏ.
3. Trả về head.next.

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):
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                l1 = l1.next
            elif l2.val < l1.val:
                l2 = l2.next
            else:
                cur.next = ListNode(l1.val)
                l1 = l1.next
                l2 = l2.next
                cur = cur.next
        return head.next

ob = Solution()
L1 = make_list([2, 4, 8])
L2 = make_list([3, 4, 8, 10])
print_list(ob.solve(L1, L2))

Đầu vào

[2, 4, 8], [3, 4, 8, 10]

Đầu ra

[4, 8, ]