Chương trình đảo ngược danh sách liên kết theo nhóm kích thước k bằng Python

Cho một danh sách liên kết đơn và giá trị k, yêu cầu đảo ngược từng nhóm k nút liên tiếp.

Ví dụ: Danh sách [1,2,3,4,5,6,7,8,9,10], k = 3 → kết quả [3, 2, 1, 6, 5, 4, 9, 8, 7, 10].

Quy trình giải quyết

1. Tạo nút giả tmp trỏ đến đầu danh sách.
2. Dùng các con trỏ prev, curr, lp, lc để quản lý việc đảo nhóm.
3. Với mỗi nhóm k nút, đảo ngược thứ tự bằng cách cập nhật con trỏ next.
4. Nối nhóm đã đảo với phần trước và sau.
5. Trả về tmp.next.

Ví dụ mã nguồn

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, node, k):
        tmp = ListNode(0)
        tmp.next = node
        prev, curr = None, node
        lp, lc = tmp, curr
        cnt = k
        while curr:
            prev = None
            while cnt > 0 and curr:
                following = curr.next
                curr.next = prev
                prev, curr = curr, following
                cnt -= 1
            lp.next, lc.next = prev, curr
            lp, lc = lc, curr
            cnt = k
        return tmp.next

ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9,10])
print_list(ob.solve(head, 3))
# Output: [3, 2, 1, 6, 5, 4, 9, 8, 7, 10, ]

Đầu vào

[1,2,3,4,5,6,7,8,9,10], 3

Đầu ra

[3, 2, 1, 6, 5, 4, 9, 8, 7, 10, ]