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

मान लीजिए हमारे पास एक लिंक्ड लिस्ट है। हमें लिंक्ड लिस्ट का पहला आधा भाग लेना है और इसे दूसरे आधे भाग पर फोल्ड करना है फिर प्रतिच्छेदी नोड्स को उनके योग लेकर मर्ज करना है। अंत में, हमें परिणामी लिंक्ड लिस्ट का हेड लौटाना है।

उदाहरण के लिए, यदि इनपुट [5,8,1,2,4,7,5] है, तो आउटपुट [2, 5, 15, 10] होगा।

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

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

• temp := 0, ptr := node से लंबाई गिनें
• t := temp // 2
• m := node, stk := []
• जब तक t शून्य नहीं:
  • m.val को stk में पुश करें
  • m.next को नल करें, m आगे बढ़ाएं
• node := m (नया हेड)
• यदि temp विषम है: m := m.next (मध्य नोड छोड़ें)
• जब तक m नल नहीं:
  • m.val += stk.pop()
  • m := m.next
• node लौटाएं

उदाहरण कोड

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, node):
        temp = 0
        ptr = node
        while ptr:
            temp += 1
            ptr = ptr.next
        t = temp // 2
        m = node
        stk = []
        while t:
            stk.append(m.val)
            tmp = m.next
            m.next = None
            m = tmp
            t -= 1
        node = m
        if temp % 2 != 0:
            m = m.next
        while m:
            m.val += stk.pop()
            m = m.next
        return node

ob = Solution()
head = make_list([5,8,1,2,4,7,5])
print_list(ob.solve(head))

इनपुट

[5,8,1,2,4,7,5]

आउटपुट

[2, 5, 15, 10, ]