পাইথনে কিছু কমন নোড সহ দুটি সাজানো লিঙ্কযুক্ত তালিকার মধ্যে একটি সর্বাধিক যোগফল লিঙ্কযুক্ত তালিকা তৈরি করুন

ধরুন আমাদের দুটি বাছাই করা লিঙ্কযুক্ত তালিকা রয়েছে, আমাদের একটি লিঙ্কযুক্ত তালিকা তৈরি করতে হবে যা স্টার্ট নোড থেকে শেষ নোড পর্যন্ত বৃহত্তম সমষ্টির পথ নিয়ে গঠিত। চূড়ান্ত তালিকায় উভয় ইনপুট তালিকার নোড থাকতে পারে।

যখন আমরা ফলাফলের তালিকা তৈরি করি, তখন আমরা শুধুমাত্র ছেদ বিন্দুর জন্য অন্য ইনপুট তালিকায় স্যুইচ করতে পারি (তালিকায় একই মান সহ দুটি নোড)। ক্রমাগত অতিরিক্ত স্থান ব্যবহার করে আমাদের এটি সমাধান করতে হবে৷

সুতরাং, যদি ইনপুট হয় [6,8,35,95,115,125], [5,8,17,37,95,105,125,135], তাহলে আউটপুট হবে [6,8,17,37,95,115,125,135]

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

• ফলাফল :=কোনোটিই নয়

• পূর্ববর্তী1 :=একটি, বর্তমান1 :=একটি

• previous2 :=b, current2 :=b

• যদিও current1 None এর মত নয় বা current2 None এর মত নয়, do

  • res1 :=0, res2 :=0

  • যদিও current1 এবং current2 শূন্য নয় এবং current1-এর ডেটা বর্তমান2-এর ডেটার মতো নয়, কর

    • যদি বর্তমান1 এর ডেটা <বর্তমান 2 এর ডেটা, তাহলে

      • res1 :=res1 + বর্তমান1 এর ডেটা

      • current1 :=current1 এর পরবর্তী

    • অন্যথায়,

      • res2 :=res2 + বর্তমান2 এর ডেটা

      • current2 :=current2 এর পরবর্তী

  • যদি বর্তমান 1 শূন্য হয়, তাহলে

    • যদিও current2 শূন্য নয়, করুন

      • res2 :=res2 + বর্তমান2 এর ডেটা

      • current2 :=current2 এর পরবর্তী

  • যদি current2 শূন্য হয়, তাহলে

    • বর্তমান 1 শূন্য না হলে, করুন

      • res1 :=res1 + বর্তমান1 এর ডেটা

      • current1 :=current1 এর পরবর্তী

  • পূর্ববর্তী1 যদি a এর মত হয় এবং পূর্ববর্তী2 b এর মত হয়, তাহলে

    • ফলাফল :=পূর্ববর্তী1 যখন (res1> res2) অন্যথায় পূর্ববর্তী2

  • অন্যথায়,

    • যদি res1> res2, তাহলে

      • পূর্ববর্তী2 এর পরের :=পূর্ববর্তী1 এর পরবর্তী

    • অন্যথায়,

      • পূর্ববর্তী1 এর পরের :=পূর্ববর্তী2 এর পরবর্তী

  • পূর্ববর্তী1 :=বর্তমান1

  • পূর্ববর্তী2 :=বর্তমান2

  • যদি current1 শূন্য না হয়, তাহলে

    • current1 :=current1 এর পরবর্তী

  • যদি current2 শূন্য না হয়, তাহলে

    • current2 :=current2 এর পরবর্তী

• ফলাফলের বিষয়বস্তু প্রদর্শন করুন।

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class LinkedList(object):
   def __init__(self, data_set = []):
      self.head = None
      if len(data_set) > 0:
         for item in data_set:
            self.insert_node(item)
   class ListNode(object):
      def __init__(self, d):
         self.data = d
         self.next = None
   def insert_node(self, new_data):
      new_node = self.ListNode(new_data)
      new_node.next = self.head
      self.head = new_node
   def find_max_sum_list(self, a, b):
      result = None
      previous1 = a
      current1 = a
      previous2 = b
      current2 = b
      while current1 != None or current2 != None:
         res1 = 0
         res2 = 0
         while current1 != None and current2 != None and current1.data != current2.data:
            if current1.data < current2.data:
               res1 += current1.data
               current1 = current1.next
            else:
               res2 += current2.data
               current2 = current2.next
         if current1 == None:
            while current2 != None:
               res2 += current2.data
               current2 = current2.next
         if current2 == None:
            while current1 != None:
               res1 += current1.data
               current1 = current1.next
         if previous1 == a and previous2 == b:
            result = previous1 if (res1 > res2) else previous2
         else:
            if res1 > res2:
               previous2.next = previous1.next
            else:
               previous1.next = previous2.next
         previous1 = current1
         previous2 = current2
         if current1 != None:
            current1 = current1.next
         if current2 != None:
            current2 = current2.next
      while result != None:
         print(result.data, end = ' ')
         result = result.next
my_list1 = LinkedList([125,115,95,35,8,6])
my_list2 = LinkedList([135,125,105,95,37,17,8,5])
my_list1.find_max_sum_list(my_list1.head, my_list2.head)

ইনপুট

[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]

আউটপুট

6 8 17 37 95 115 125 135