โปรแกรมจัดเรียงโหนด linked list ตามค่า k ใน Python

สมมติว่ามี singly linked list และค่า k ต้องจัดเรียงโหนด: ค่าน้อยกว่า k ก่อน, เท่ากับ k กลาง, มากกว่า k ท้าย โดยรักษาลำดับสัมพัทธ์เดิม

ตัวอย่าง: L = [4,3,6,6,6,10,8], k = 6 ผลลัพธ์ [4,3,6,6,6,10,8]

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

1. สร้าง dummy head 3 ตัว: less_head, equal_head, greater_head
2. วน cur ผ่านลิสต์:
   • ถ้า cur.val < k: เพิ่มท้าย less
   • ถ้า cur.val > k: เพิ่มท้าย greater
   • มิฉะนั้น: เพิ่มท้าย equal
3. เชื่อม less.next = equal_head.next, equal.next = greater_head.next
4. คืน less_head.next

ตัวอย่างโค้ด

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):
        less_head = less = ListNode(0)
        equal_head = equal = ListNode(0)
        greater_head = greater = ListNode(0)
        cur = node
        while cur:
            if cur.val < k:
                less.next = ListNode(cur.val)
                less = less.next
            elif cur.val > k:
                greater.next = ListNode(cur.val)
                greater = greater.next
            else:
                equal.next = ListNode(cur.val)
                equal = equal.next
            cur = cur.next
        less.next = equal_head.next
        equal.next = greater_head.next
        return less_head.next

ob = Solution()
L = make_list([4, 3, 6, 6, 6, 10, 8])
k = 6
print_list(ob.solve(L, k))

อินพุต

[4, 3, 6, 6, 6, 10, 8], 6

เอาต์พุต

[4, 3, 6, 6, 6, 10, 8, ]