2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode
問題
２つのLinkedListが与えられ、２つが交差する点を見つける問題
解法
HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。
以下の２つの処理を同時に行う
- リストAを順番に先頭から見ていき、末尾までいったらリストBの先頭に進む。
- リストBを順番に先頭見ていき、末尾まで行ったらAの先頭に進む。
すると交差していたら同じタイミング交差点を通化することになる。
