पायथन में दो दी गई लिंक्ड लिस्ट का यूनियन खोजने का प्रोग्राम

मान लीजिए हमारे पास दो सॉर्टेड लिंक्ड लिस्ट L1 और L2 हैं, हमें एक नई सॉर्टेड लिंक्ड लिस्ट लौटानी है जो दोनों दी गई लिस्ट का यूनियन है।

उदाहरण के लिए, यदि इनपुट L1 = [10,20,30,40,50,60,70] और L2 = [10,30,50,80,90] है, तो आउटपुट [10, 20, 30, 40, 50, 60, 70, 80, 90] होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (मर्ज जैसी रिकर्सन):

• एक फंक्शन solve() परिभाषित करें जो L1, L2 लेता है
• यदि L1 खाली है: L2 लौटाएं
• यदि L2 खाली है: L1 लौटाएं
• यदि L1.val < L2.val:
  • res := L1, res.next := solve(L1.next, L2)
• अन्यथा यदि L2.val < L1.val:
  • res := L2, res.next := solve(L2.next, L1)
• अन्यथा (बराबर):
  • res := L1, res.next := solve(L1.next, L2.next)
• res लौटाएं

उदाहरण कोड

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, L1, L2):
        if not L1:
            return L2
        if not L2:
            return L1
        if L1.val < L2.val:
            res = L1
            res.next = self.solve(L1.next, L2)
        elif L2.val < L1.val:
            res = L2
            res.next = self.solve(L2.next, L1)
        else:
            res = L1
            res.next = self.solve(L1.next, L2.next)
        return res

ob = Solution()
L1 = make_list([10,20,30,40,50,60,70])
L2 = make_list([10,30,50,80,90])
print_list(ob.solve(L1, L2))

इनपुट

[10,20,30,40,50,60,70], [10,30,50,80,90]

आउटपुट

[10, 20, 30, 40, 50, 60, 70, 80, 90, ]