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

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

इसलिए, यदि इनपुट एल =[4, 3, 6, 6, 6, 10, 8] के =6 जैसा है, तो आउटपुट [4, 3, 6, 6, 6, 10, 8, ]<होगा। /पी>

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• less_head :=0 के समान मान के साथ एक लिंक्ड सूची नोड बनाएं
• कम:=कम_सिर
• equal_head :=0 के समान मान के साथ एक लिंक्ड सूची नोड बनाएं
• बराबर:=बराबर_सिर
• greater_head :=0 के समान मान के साथ एक लिंक्ड सूची नोड बनाएं
• अधिक :=ग्रेटर_हेड
• cur:=नोड
• जबकि वक्र शून्य नहीं है, करें
  • यदि वक्र का मान
  • कम के आगे :=एक लिंक्ड सूची नोड बनाएं जिसका मान cur के मान के समान हो
  • कम :=कम का अगला
• अन्यथा जब cur का मान> k, तब
  • अधिक से अधिक :=एक लिंक्ड सूची नोड बनाएं जिसका मान cur के मान के समान हो
  • बड़ा :=बड़ा का अगला
• अन्यथा,
  • बराबर के आगे :=एक लिंक्ड सूची नोड बनाएं जिसका मान cur के मान के समान हो
  • बराबर :=बराबर का अगला
• cur :=cur के आगे

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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