用 Python 编写程序，从给定的链接列表中查找折叠列表

pythonserver side programmingprogramming

假设我们有一个链接列表。我们必须取链接列表的前半部分，折叠后半部分，然后通过求和合并相交节点。最后，我们必须返回链表的结果头。

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

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

temp := 0
ptr := node
当 ptr 不为空时，执行
- temp := temp + 1
- ptr := next of ptr
t := quotient of temp / 2
m := node
stk := a new stack
当 t 非零时，执行
- 将 m 的值推送到 stk 中
- tmp := next of m
- next of m := null
- m := tmp
- t := t - 1
node := m
如果 temp 为偶数，则
- m := next of m
当 m 不为 null 时，执行
- value of m := value of m + stack top element.
- pop from stk
- m := next of 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))