Chương trình chèn phần tử mới vào linked list trước vị trí cho trước trong Python

Cho danh sách các phần tử lưu trong singly linked list. Cho vị trí pos và giá trị val. Chèn val trước chỉ số pos của linked list.

Ví dụ: nums = [1,5,3,6,8], pos = 3, val = 7 → kết quả [1,5,3,7,6,8].

Thuật toán giải quyết

1. Tạo node mới new với giá trị val
2. Nếu pos == 0: new.next = head, trả về new
3. Duyệt từ head đến vị trí pos-1 (node temp)
4. new.next = temp.next, temp.next = new
5. Trả về head

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(list_head, pos, val):
    new = ListNode(val)
    if pos == 0:
        new.next = list_head
        return new
    temp = list_head
    while temp and pos != 1:
        temp = temp.next
        pos -= 1
    new.next = temp.next
    temp.next = new
    return list_head

nums = [1,5,3,6,8]
pos = 3
val = 7
list_head = make_list(nums)
list_head = solve(list_head, pos, val)
print_list(list_head)

Đầu vào

[1,5,3,6,8], 3, 7

Đầu ra

[1, 5, 3, 7, 6, 8, ]