โปรแกรมกลับลำดับลิงก์ลิสต์เป็นกลุ่มขนาด k ใน Python

สมมติว่าเรามีลิงก์ลิสต์แบบเดี่ยว (singly linked list) และค่า k เราต้องกลับลำดับทุกกลุ่มที่ติดกัน k โหนด

ตัวอย่าง: List = [1,2,3,4,5,6,7,8,9,10], k = 3 ผลลัพธ์คือ [3, 2, 1, 6, 5, 4, 9, 8, 7, 10]

ขั้นตอนการแก้ปัญหา

1. สร้างโหนด dummy tmp ค่า 0, tmp.next = node
2. กำหนด prev = None, curr = node
3. lp = tmp, lc = curr, cnt = k
4. วนลูป while curr ไม่ใช่ None:
   • prev = None
   • วนลูป while cnt > 0 และ curr ไม่ใช่ None:
     • following = curr.next
     • curr.next = prev
     • prev = curr, curr = following
     • cnt -= 1
   • lp.next = prev, lc.next = curr
   • lp = lc, lc = curr
   • cnt = k
5. คืนค่า tmp.next

ตัวอย่างโค้ด 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(']')

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

อินพุต / เอาต์พุต

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

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