โปรแกรมผสาน Linked List สองอันสลับกัน (Interleave) ใน Python

สมมติว่าเรามี linked list สองอัน l1 และ l2 เราต้องคืนค่า linked list เดียวโดยผสานองค์ประกอบสลับกันเริ่มจาก l1 หากเหลือโหนดใน list ใด list หนึ่ง ให้ต่อท้ายไป

ตัวอย่าง: l1 = [5,4,6,3,4,7], l2 = [8,6,9] ผลลัพธ์: [5,8,4,6,6,9,3,4,7]

ขั้นตอนการแก้ปัญหา (In-place Insertion)

1. ans = l1
2. วนลูป while l2 ไม่ใช่ null:
   • หาก ans ไม่ใช่ null และ ans.next ไม่ใช่ null:
     • สร้าง newnode จาก l2.val
     • แทรก newnode ระหว่าง ans และ ans.next
     • เลื่อน ans = newnode.next, l2 = l2.next
   • หาก ans.next เป็น null: ต่อ l2 ท้าย ans และ break
   • หาก ans เป็น null: คืนค่า l2
3. คืนค่า l1

ตัวอย่างโค้ด 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):
        ans = l1
        while l2:
            if ans:
                if ans.next:
                    newnode = ListNode(l2.val)
                    newnode.next = ans.next
                    ans.next = newnode
                    ans = newnode.next
                    l2 = l2.next
                else:
                    ans.next = l2
                    break
            else:
                return l2
        return l1

ob = Solution()
l1 = make_list([5, 4, 6, 3, 4, 7])
l2 = make_list([8, 6, 9])
res = ob.solve(l1, l2)
print_list(res)  # Output: [5, 8, 4, 6, 6, 9, 3, 4, 7, ]

อินพุต

[5, 4, 6, 3, 4, 7], [8, 6, 9]

เอาต์พุต

[5, 8, 4, 6, 6, 9, 3, 4, 7, ]