从给定的Python链接列表中找到折叠列表的程序

假设我们有一个链接列表。我们必须取链接列表的前半部分并将其折叠在第二半部分上，然后通过取它们的总和合并交叉节点。最后，我们必须返回链接列表的结果头。

因此，如果输入为[5,8,1,2,4,7,5]，则输出将为[2, 5, 15, 10,]

为了解决这个问题，我们将遵循以下步骤−

temp：= 0
ptr：= node
当ptr非null时，执行以下操作
- temp: = temp + 1
- ptr：=ptr的下一个
t：= temp/2的商
m：= node
stk：=一个新的堆栈
当t非零时，执行以下操作
- push m的值到stk中
- tmp：= m的下一个
- m的下一个：= null
- m：= tmp
- t：= t-1
node：= m
如果temp为偶数，则
- m：= m的下一个
当m不为null时，执行以下操作
- m的值：= m的值+堆栈顶部元素。
- pop from stk
- m：= m的下一个
返回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))