Pythonで連結リストを「折りたたんで」マージするプログラムの実装方法

問題の概要

連結リスト（Linked List）が与えられたとします。まずリストの前半を切り離し、それを後半に対して折り返すように重ね合わせます。そして、重なり合うノード同士の値を合計してマージし、最終的にできあがった連結リストの先頭ノード（head）を返します。

たとえば、入力が [5, 8, 1, 2, 4, 7, 5] の場合、出力は [2, 5, 15, 10] になります。

この例では、前半の「5, 8, 1」と後半の「4, 7, 5」が対応します（リスト長が奇数のため、中央のノード「2」はスキップされます）。折りたたみでは前半の末尾と後半の先頭がペアになるため、1+4=5、8+7=15、5+5=10 という計算が行われ、先頭には中央ノードの「2」がそのまま残ります。

アルゴリズムの手順

• カウンタ temp を 0、ポインタ ptr を先頭ノードで初期化します。
• ptr が null になるまで temp を増やしながらノードを辿り、リスト全体の長さを数えます。
• 半分の長さ t = temp // 2 を求めます。
• ポインタ m を先頭ノードにセットし、空のスタック stk を用意します。
• t が 0 になるまで次の処理を繰り返します。
  • m の値をスタックにプッシュする
  • 次ノードへの参照を一時変数に退避させ、現在のノードの next を null にしてリンクを切断する
  • m を次のノードへ進め、t を 1 減らす
• node を m（＝後半部分の先頭ノード）に更新します。
• リスト長が奇数の場合は中央ノードを計算対象から外すため、m を一つ先へ進めます。
• m が null になるまで、「スタックから値を pop して m の値に加算 → m を次へ進める」を繰り返します。
• 結果となる先頭ノード node を返します。

なぜスタックを使うのか

紙を折るとき、折り目を挟んで両側の端同士がくっつきますよね。連結リストでも同じように、前半の末尾ノードと後半の先頭ノードが最初にペアになります。前半の値を順にスタックへ積んでおけば、LIFO（後入れ先出し）の性質によって、後半を先頭から走査しながら自然に逆順の値を取り出せるのです。

計算量についても触れておくと、リストの走査は全体の長さを数えるパスとマージのパスの2回のみなので、時間計算量は O(n)。スタックには前半分の値だけを保持するため、追加メモリも O(n) で抑えられます。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

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
      # スタックの値をpopしながら加算してマージ
      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]

まとめ

このアルゴリズムのポイントは、前半の切り離しとスタックへの退避を同時に行うことです。これにより、余分な走査なしに「折りたたみ」の構造を効率よく再現できます。偶数長・奇数長どちらのリストにも対応しており、連結リストの操作練習としても非常に良い題材です。