Chương trình hoán vị nút trong danh sách liên kết trong Python

Mô tả bài toán

Cho danh sách liên kết L và giá trị k. Hoán vị nút thứ k từ đầu và nút thứ k từ cuối. Trả về danh sách sau hoán vị.

Ví dụ

L = [1,5,6,7,1,6,3,9,12], k = 3 -> [1,5,3,7,1,6,6,9,12] (nút 3 từ đầu là 6, từ cuối là 3).

Giải thuật

1. Duyệt đến nút thứ k từ đầu -> firstNode.
2. Dùng hai con trỏ: temp từ firstNode, secondNode từ head. Khi temp đến cuối, secondNode sẽ ở nút thứ k từ cuối.
3. Hoán vị giá trị firstNode.val và secondNode.val.

Triển khai 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(L, k):
    temp = L
    for i in range(k - 1):
        temp = temp.next
    firstNode = temp
    secondNode = L
    while temp.next:
        secondNode = secondNode.next
        temp = temp.next
    firstNode.val, secondNode.val = secondNode.val, firstNode.val
    return L

L = [1, 5, 6, 7, 1, 6, 3, 9, 12]
k = 3
print_list(solve(make_list(L), k))

Đầu vào

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

Đầu ra

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