Chương trình gộp hai danh sách liên kết tại vị trí giữa trong Python

Cho 2 danh sách liên kết L1 (dài m) và L2 (dài n), vị trí a, b. Xóa nút từ a đến b trong L1, chèn L2 vào giữa.

Ví dụ: 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].

Giải thuật

1. Tìm đuôi tail2 của L2.
2. Duyệt L1 đếm chỉ số, tìm end1 (trước a) và start3 (sau b).
3. Nối: end1.next = head2, tail2.next = start3.
4. Trả về L1.

Ví dụ minh họa

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, b = 3, 6
print_list(solve(make_list(L1), make_list(L2), a, b))

Đầu vào

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

Đầu ra

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