পাইথনে k মানের উপর ভিত্তি করে লিঙ্কযুক্ত তালিকা নোডগুলি সাজানোর প্রোগ্রাম

ধরুন আমাদের একটি এককভাবে লিঙ্ক করা তালিকা এবং আরেকটি মান k আছে। আমাদের নোডগুলিকে এমনভাবে সাজাতে হবে যাতে সমস্ত নোডের মানগুলি k-এর চেয়ে কম প্রথমে আসে, এবং সমস্ত নোডের মানগুলি k এর পরের সমান এবং সবশেষে অন্যান্য নোডগুলি সবশেষে আসে। সীমাবদ্ধতা হল নোডগুলির আপেক্ষিক ক্রম একই থাকা উচিত।

সুতরাং, যদি ইনপুট হয় L =[4, 3, 6, 6, 6, 10, 8] k =6, তাহলে আউটপুট হবে [4, 3, 6, 6, 6, 10, 8, ]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• less_head :=0 এর মতো মান সহ একটি লিঙ্কযুক্ত তালিকা নোড তৈরি করুন
• কম :=কম_হেড
• equal_head :=0 এর মতো মান সহ একটি লিঙ্কযুক্ত তালিকা নোড তৈরি করুন
• সমান :=equal_head
• greater_head :=0 এর মতো মান সহ একটি লিঙ্কযুক্ত তালিকা নোড তৈরি করুন
• বৃহত্তর :=greater_head
• cur :=নোড
• যদিও cur নাল না হয়, do
  • যদি 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, ]