पायथन में मान k के आधार पर लिंक्ड लिस्ट नोड्स को व्यवस्थित करने का प्रोग्राम

मान लीजिए हमारे पास एक सिंगली लिंक्ड लिस्ट और एक मान k है। हमें नोड्स को इस तरह व्यवस्थित करना है कि जिन नोड्स के मान k से कम हैं वे पहले आएं, फिर जिनके मान k के बराबर हैं, और अंत में बाकी नोड्स। प्रतिबंध यह है कि नोड्स का सापेक्ष क्रम समान रहना चाहिए।

उदाहरण के लिए, यदि इनपुट L = [4, 3, 6, 6, 6, 10, 8] और k = 6 है, तो आउटपुट [4, 3, 6, 6, 6, 10, 8] होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (तीन सूचियों में विभाजन):

• less_head, equal_head, greater_head डमी नोड्स बनाएं
• less, equal, greater पॉइंटर्स इनके हेड पर
• cur := node से ट्रैवर्स करें:
  • यदि cur.val < k: less.next = ListNode(cur.val), less आगे बढ़ाएं
  • यदि cur.val > k: greater.next = ListNode(cur.val), greater आगे बढ़ाएं
  • अन्यथा: equal.next = ListNode(cur.val), equal आगे बढ़ाएं
  • cur = cur.next
• सूचियों को जोड़ें: less.next = equal_head.next, equal.next = greater_head.next
• 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, ]