पायथन में कुछ सामान्य नोड्स वाली दो क्रमबद्ध लिंक्ड सूचियों में से एक अधिकतम सम लिंक्ड सूची का निर्माण करें

मान लीजिए कि हमारे पास दो क्रमबद्ध लिंक्ड सूचियां हैं, हमें एक लिंक्ड सूची बनानी होगी जिसमें प्रारंभ नोड से अंत नोड तक सबसे बड़ा योग पथ हो। अंतिम सूची में दोनों इनपुट सूचियों के नोड शामिल हो सकते हैं।

जब हम परिणाम सूची बना रहे होते हैं, तो हम केवल प्रतिच्छेदन बिंदु (सूचियों में समान मान वाले दो नोड) के लिए अन्य इनपुट सूची पर स्विच कर सकते हैं। हमें निरंतर अतिरिक्त स्थान का उपयोग करके इसे हल करना होगा।

इसलिए, यदि इनपुट [6,8,35,95,115,125], [5,8,17,37,95,105,125,135] जैसा है, तो आउटपुट [6,8,17,37,95,115,125,135]

होगा।

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

परिणाम:=कोई नहीं
पिछला1:=ए, वर्तमान1:=ए
पिछला2 :=b, current2 :=b
जबकि current1 कोई नहीं के समान नहीं है या current2 कोई नहीं के समान नहीं है, करें
- रेस1:=0, रेस2:=0
- जबकि current1 और current2 शून्य नहीं हैं और current1 का डेटा current2 के डेटा के समान नहीं है, करें
  - अगर current1 का डेटा
    - res1 :=res1 + current1 का डेटा
    - current1 :=current1 के आगे
  - अन्यथा,
    - res2 :=res2 + current2 का डेटा
    - current2 :=current2 के आगे
- अगर current1 शून्य है, तो
  - जबकि current2 शून्य नहीं है, करें
    - res2 :=res2 + current2 का डेटा
    - current2 :=current2 के आगे
- अगर current2 शून्य है, तो
  - जबकि current1 शून्य नहीं है, करें
    - res1 :=res1 + current1 का डेटा
    - current1 :=current1 के आगे
- अगर पिछला1 ए के समान है और पिछला2 बी के समान है, तो
  - परिणाम :=पिछला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