Pythonで片方向リンクリストの中央ノードを1回の走査で見つける方法

片方向リンクリスト（単方向連結リスト）の先頭ノードが与えられたとき、その中央ノードの値を求めることを考えます。ノード数が偶数で中央にあたるノードが2つ存在する場合は、後ろ側（2番目）の中央ノードを返すものとします。さらに、リスト全体をたどるのは1回だけ（シングルパス）で解くのが条件です。

例えば、入力が [5,9,6,4,8,2,1,4,5,2] の場合、要素数は10なので中央は「8」と「2」の2つになります。したがって、出力は後ろ側の 2 となります。

解法のアプローチ

この問題は、基準点となるポインタ p をゆっくり進めながら、カウンタを組み合わせて処理することで解けます。手順は以下の通りです。

• p を先頭ノードに設定し、カウンタ d と l をそれぞれ 0 で初期化します。
• node が null になるまで、次の処理を繰り返します。
  • d が 2 以外の場合：node を次のノードへ進め、l と d をそれぞれ 1 ずつ増やします。
  • d が 2 の場合：p を次のノードへ進め、d を 0 に戻します。
• ループ終了後、l が奇数であれば p の値を、偶数であれば p の次のノードの値を返します。

それでは、実際の実装例を見てみましょう。

実装例

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

class Solution:
   def solve(self, node):
      p = node
      d = 0
      l = 0
      while node:
         if d != 2:
            node = node.next
            l += 1
            d += 1
         else:
            p = p.next
            d = 0
      return p.val if l & 1 else p.next.val

ob = Solution()
head = make_list([5,9,6,4,8,2,1,4,5,2])
print(ob.solve(head))

入力

[5,9,6,4,8,2,1,4,5,2]

出力

2

よりシンプルな別解：低速・高速ポインタ（Runner法）

同じ問題は、いわゆる「低速・高速ポインタ」を使うとより簡潔に書けます。slow ポインタは1つずつ、fast ポインタは2つずつ進めます。fast がリストの末尾に到達したとき、slow はちょうど中央（偶数長の場合は後ろ側の中央）に位置しています。

class Solution:
   def solve(self, node):
      slow = fast = node
      while fast and fast.next:
         slow = slow.next
         fast = fast.next.next
      return slow.val

ob = Solution()
head = make_list([5,9,6,4,8,2,1,4,5,2])
print(ob.solve(head))

どちらの手法も計算量は O(n)、追加メモリは O(1) であり、シングルパスの条件を満たします。実務やコーディング面接では、可読性の高い Runner法が好まれることが多いです。