Python में लिंक्ड लिस्ट को बीच में मर्ज करने का प्रोग्राम

मान लीजिए हमारे पास दो लिंक्ड लिस्ट L1 और L2 हैं जिनकी लंबाई m और n है, हमारे पास दो पोजीशन a और b भी हैं। हमें L1 से aवें नोड से bवें नोड तक नोड्स को हटाना है और बीच में L2 को मर्ज करना है।

उदाहरण के लिए, यदि इनपुट है L1 = [1,5,6,7,1,6,3,9,12], L2 = [5,7,1,6], a = 3, b = 6, तो आउटपुट [1, 5, 6, 5, 7, 1, 6, 9, 12] होगा।

समाधान के चरण

1. head2 := L2, temp := L2
2. while temp.next:
   • temp := temp.next
3. tail2 := temp
4. count := 0
5. temp := L1
6. end1 := None, start3 := None
7. while temp:
   • यदि count == a-1:
     • end1 := temp
   • यदि count == b+1:
     • start3 := temp
     • लूप से बाहर निकलें
   • temp := temp.next
   • count := count + 1
8. end1.next := head2
9. tail2.next := start3
10. L1 वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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(']')

def solve(L1, L2, a, b):
    head2 = temp = L2
    while temp.next:
        temp = temp.next
    tail2 = temp
    count = 0
    temp = L1
    end1, start3 = None, None
    while temp:
        if count == a-1:
            end1 = temp
        if count == b+1:
            start3 = temp
            break
        temp = temp.next
        count += 1
    end1.next = head2
    tail2.next = start3
    return L1

L1 = [1,5,6,7,1,6,3,9,12]
L2 = [5,7,1,6]
a = 3
b = 6
print_list(solve(make_list(L1), make_list(L2), a, b))

इनपुट

[1,5,6,7,1,6,3,9,12], [5,7,1,6], 3, 6

आउटपुट

[1, 5, 6, 5, 7, 1, 6, 9, 12, ]