目次
解いた問題
leetcode 160: Intersection of Two Linked Lists
2つのリストがあり、内部的に結合しているかもしれないからどのノードで結合してるか検知してねって問題。
学び
- 2ポインタ法は走査を複数回やる前提で考えるとうまく解けそう
- AIに聞くときは「答えださないで」と先に言っておかないと結論ファーストでネタバレを食らう
最初に考えた解法
前回のウサギと亀は使えなさそうだけどまた2ポインタ法の応用かなと考えた。
listAとlistBを走査するポインタをそれぞれ用意して、二つの値が一致したらそのあとの値を確認し、一致するなら交差した、と言えないかなと考えた。
while文においてどのように条件を書いたらちゃんと回るかをAIで調べようと思ったら「答えだすな」というプロンプトを書き忘れて正解が出てしまった。それが下記。
正解
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a
2ポインタ法を使っているものの自分が考えていたものとは全く異なる設計。
あまり理解できなかったので調べてみた。
全体像の確認
使っている技術は2ポインタ法と三項演算子。
2ポインタ法は下記参照。
https://zenn.dev/zenn_mita/articles/67834a5b3c0760
三項演算子とはPython独自の条件付代入でa = A if 条件 else Bの形でよく使われるものです。
三項演算子を使わないと下記のようになる。
if 条件:
a = A
else:
a = B
つまり、「条件」がTrueならAを、FalseならBをaに代入するというのを1行で書いている文法です。
if elseで何をしているのか
三項演算子の具体的な処理を見てみます。
a = a.next if a else headBというのは、「a(すなわちlistAのポインタ)がNoneじゃない」ときにはaのポインタを次にずらして、「aがNone」のときheadBを入れる、という処理です。
ここでよくわからないのが「なぜheadBをいれる？」という点。
これはlistAとlistBの長さが異なるので、走査する数を一致させ同一タイミングで交差ノードに差し掛からせるための仕組みのよう。
listAを走査する長さをx, listBを走査する長さをyとしたら、listAを走査した後にlistBを走査したときの全走査数はx + y であり、B→Aのときも同様にy + xとなる。
すなわち同様の距離を走ったことになる。
そうするとどちらかのリストを走査した後の走査は必ず同一階層で操作するようになるため、交差ノードが存在すると必ずそのノードを同時タイミングで指すことになる、という仕組み。
わかりづらいなと自分で思ったので下記図を参考に。
Aの2つ目の1とBの3が同一階層、という認識。
a is not bって交差ノードないときエラー出ない？
上記で交差ノードがあったらそこを返すようになっているのは理解できたが、なかった場合どっちもNoneになりa is not bをずっと満たして無限ループするのでは？と思いました。
調べてみたところ、PythonにおけるNoneは「シングルトン」となっており、どのNoneを指しても同一オブジェクト扱いになるため、必ずループは抜けるようになっているそう。
よく考えられているなぁ。
結論
それぞれのリストを2回ずつ交互に走査することによって見るノードの階層をそろえ、交差ノードの見地となかった場合の処理を簡単にまとめているのが本2ポインタ法だった。
感想
む、むずかしい、、、。
ウサギと亀もそうだったが、2ポインタ法は1回の走査で終わらせず複数回走査することを意識するとよりうまく溶けそうだと感じました。
下記ウサギと亀のアルゴリズム
https://zenn.dev/zenn_mita/articles/fe0e6b6b79e18e
引き続き継続します！