Chương trình xen kẽ phần tử từ hai danh sách liên kết trong Python

Cho hai danh sách liên kết và , xen kẽ các nút bắt đầu từ . Nút dư thừa nối vào cuối.

Ví dụ: , → [5,8,4,6,6,9,3,4,7].

Giải thuật (Chèn nút l2 vào giữa các nút l1)

1. .
2. Khi không rỗng:
   • Nếu và tồn tại: tạo nút mới từ , chèn sau , di chuyển qua nút mới, .
   • Nếu là None: nối , break.
3. Trả về .

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(']')

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, ]

Đầu vào

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

Đầu ra

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