Pythonで連結リストの後ろからK番目のノードを見つけるプログラム

問題概要

片方向連結リストが与えられたとき、後ろからk番目のノード(0始まりのインデックス)の値を求めることを考えます。ただし、この問題はリストを1回の走査(シングルパス)で解く必要があります。

例えば、入力が node = [5,4,6,3,4,7]、k = 2 の場合、出力は 3 になります。これは、後ろから2番目(インデックス3)のノードの値が3であるためです。

解法のアプローチ:2ポインタ技法

この問題を効率的に解くには、2つのポインタを使う手法が有効です。片方のポインタを先にkステップだけ進めておき、その後両方のポインタを同時に末尾へ向けて進めます。先頭のポインタが末尾に到達したとき、もう片方のポインタが指しているのが後ろからk番目のノードです。

具体的には、以下の手順に従います。

• klast を node(先頭ノード)に設定します。

• last も node(先頭ノード)に設定します。

• i が 0 から k までの間、以下を繰り返します。

  • last を次のノードに進めます。

• last の次のノードが存在する間、以下を繰り返します。

  • last を次のノードに進めます。

  • klast も次のノードに進めます。

• klast の値を返します。

このアルゴリズムの計算量は時間 O(n)、空間 O(1) であり、リスト全体を事前に走査して長さを求める必要がないため、1回のパスで目的のノードに到達できます。

実装例

理解を深めるために、以下の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

class Solution:
   def solve(self, node, k):
      klast = node
      last = node
      for i in range(k):
         last = last.next
      while last.next:
         last = last.next
         klast = klast.next
      return klast.val

ob = Solution()
l1 = make_list([5,4,6,3,4,7])
print(ob.solve(l1, 2))

入力

[5,4,6,3,4,7], 2

出力

3

まとめ

このように、2つのポインタの距離をkだけ保ちながら同時に進めることで、連結リストの長さを事前に知らなくても、後ろからk番目のノードの値を1回の走査だけで取得できます。面接やコーディングテストで頻出のテクニックなので、ぜひ覚えておきましょう。