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

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

उदाहरण के लिए, यदि इनपुट L1 = [2, 4, 8] और L2 = [3, 4, 8, 10] है, तो आउटपुट [4, 8] होगा।

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

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (टू-पॉइंटर):

• head := ListNode(0), cur := head
• जब तक l1 और l2 खाली नहीं हैं:
  • यदि l1.val < l2.val: l1 = l1.next
  • अन्यथा यदि l2.val < l1.val: l2 = l2.next
  • अन्यथा (बराबर):
    • cur.next = ListNode(l1.val)
    • l1 = l1.next, l2 = l2.next
    • cur = cur.next
• head.next लौटाएं

उदाहरण कोड

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):
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                l1 = l1.next
            elif l2.val < l1.val:
                l2 = l2.next
            else:
                cur.next = ListNode(l1.val)
                l1 = l1.next
                l2 = l2.next
                cur = cur.next
        return head.next

ob = Solution()
L1 = make_list([2, 4, 8])
L2 = make_list([3, 4, 8, 10])
print_list(ob.solve(L1, L2))

इनपुट

[2, 4, 8], [3, 4, 8, 10]

आउटपुट

[4, 8, ]