Pythonで特定のリンクリストから折りたたまれたリストを見つけるプログラム

リンクリストがあるとします。リンクリストの前半を取得し、後半を折りたたんでから、交差するノードの合計を取得してマージする必要があります。最後に、リンクリストの結果の先頭を返す必要があります。

したがって、入力が[5,8,1,2,4,7,5]の場合、出力は[2、5、15、10、]

これを解決するには、次の手順に従います-

• temp：=0
• ptr：=ノード
• ptrがnullでない場合は、
  • temp：=temp + 1
  • ptr：=ptrの次
• t：=温度の商/ 2
• m：=ノード
• stk：=新しいスタック
• tがゼロ以外の場合は、
  • mの値をstkにプッシュ
  • tmp：=mの次
  • mの次：=null
  • m：=tmp
  • t：=t-1
• node：=m
• 温度が偶数の場合、
  • m：=mの次
• mがnullでない場合は、
  • mの値：=mの値+スタックトップ要素。
  • stkからポップ
  • m：=mの次
• リターンノード

理解を深めるために、次の実装を見てみましょう-

例

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, ]