पायथन में दो सॉर्टेड लिंक्ड लिस्ट से मैक्सिमम सम लिंक्ड लिस्ट बनाना

समस्या विवरण

दो सॉर्टेड लिंक्ड लिस्ट दी गई हैं, एक लिंक्ड लिस्ट बनाएं जिसमें स्टार्ट से एंड तक का सबसे बड़ा सम पथ हो। परिणाम दोनों इनपुट लिस्ट के नोड्स से बन सकता है। केवल कॉमन नोड्स (समान मान) पर स्विच कर सकते हैं। O(1) अतिरिक्त स्पेस में हल करें।

उदाहरण

लिस्ट 1: [6, 8, 35, 95, 115, 125]

लिस्ट 2: [5, 8, 17, 37, 95, 105, 125, 135]

आउटपुट: [6, 8, 17, 37, 95, 115, 125, 135]

एल्गोरिदम

1. दो पॉइंटर्स current1, current2 और उनके previous पॉइंटर्स रखें
2. जब तक दोनों खत्म न हों:
   • कॉमन नोड तक प्रत्येक पथ का योग res1, res2 गिनें
   • जिस पथ का योग अधिक हो, उसे चुनें (पॉइंटर्स जोड़कर)
   • कॉमन नोड पर previous पॉइंटर्स अपडेट करें
3. परिणाम लिस्ट का हेड वापस करें

पायथन कार्यान्वयन

class LinkedList:
    class ListNode:
        def __init__(self, d):
            self.data = d
            self.next = None
    def __init__(self, data_set=[]):
        self.head = None
        for item in data_set:
            self.insert_node(item)
    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
        prev1, curr1 = a, a
        prev2, curr2 = b, b
        while curr1 or curr2:
            res1 = res2 = 0
            while curr1 and curr2 and curr1.data != curr2.data:
                if curr1.data < curr2.data:
                    res1 += curr1.data
                    curr1 = curr1.next
                else:
                    res2 += curr2.data
                    curr2 = curr2.next
            if not curr1:
                while curr2:
                    res2 += curr2.data
                    curr2 = curr2.next
            if not curr2:
                while curr1:
                    res1 += curr1.data
                    curr1 = curr1.next
            if prev1 == a and prev2 == b:
                result = prev1 if res1 > res2 else prev2
            else:
                if res1 > res2:
                    prev2.next = prev1.next
                else:
                    prev1.next = prev2.next
            prev1, prev2 = curr1, curr2
            if curr1: curr1 = curr1.next
            if curr2: curr2 = curr2.next
        while result:
            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