โปรแกรมรวม linked list ระหว่างตำแหน่ง a ถึง b ใน Python

ปัญหา

Linked list L1 และ L2 ความยาว m,n มีตำแหน่ง a,b ลบโหนด L1 จาก a ถึง b แล้วแทรก L2 เข้าไปตรงกลาง

ตัวอย่าง

L1=[1,5,6,7,1,6,3,9,12], L2=[5,7,1,6], a=3, b=6 → [1,5,6,5,7,1,6,9,12]

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

1. head2 := L2, temp := L2 หา tail2 (โหนดสุดท้ายของ L2)
2. count:=0, temp:=L1, end1:=None, start3:=None
3. เดิน temp:
   • ถ้า count == a-1: end1 := temp
   • ถ้า count == b+1: start3 := temp; break
   • temp = temp.next; count += 1
4. end1.next = head2; tail2.next = start3
5. คืน 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(']')

def solve(L1, L2, a, b):
    head2 = temp = L2
    while temp.next:
        temp = temp.next
    tail2 = temp
    count = 0
    temp = L1
    end1, start3 = None, None
    while temp:
        if count == a-1:
            end1 = temp
        if count == b+1:
            start3 = temp
            break
        temp = temp.next
        count += 1
    end1.next = head2
    tail2.next = start3
    return L1

L1 = [1,5,6,7,1,6,3,9,12]
L2 = [5,7,1,6]
a = 3
b = 6
print_list(solve(make_list(L1), make_list(L2), a, b))

อินพุต

[1,5,6,7,1,6,3,9,12], [5,7,1,6], 3, 6

เอาต์พุต

[1, 5, 6, 5, 7, 1, 6, 9, 12, ]