โปรแกรมหาจุดตัดของ linked list 2 ตัวใน Python

สมมติว่ามี linked list เรียงแล้ว L1 และ L2 ต้องการสร้าง linked list ใหม่ที่เป็น intersection (ค่าที่ปรากฏในทั้งสอง)

ตัวอย่าง: L1 = [2,4,8], L2 = [3,4,8,10] ผลลัพธ์ [4,8]

ขั้นตอนการแก้ปัญหา

1. head = cur = ListNode(0)
2. วนลูป بينما l1 และ l2 ไม่ว่าง:
   • ถ้า l1.val < l2.val: l1 = l1.next
   • ถ้า l2.val < l1.val: l2 = l2.next
   • มิฉะนั้น (เท่ากัน): เพิ่มโหนดใหม่ค่า l1.val ท้าย cur, ขยับ l1, l2, cur
3. คืน head.next

ตัวอย่างโค้ด

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))

อินพุต

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

เอาต์พุต

[4, 8, ]