2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode

問題

2つのLinkedListが与えられ、2つが交差する点を見つける問題

leetcode.com

解法

HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。

以下の2つの処理を同時に行う

  • リストAを順番に先頭から見ていき、末尾までいったらリストBの先頭に進む。
  • リストBを順番に先頭見ていき、末尾まで行ったらAの先頭に進む。

すると交差していたら同じタイミング交差点を通化することになる。

ソースコード