Intersection of Two Linked Lists
2つの単方向連結リストが、1つのノードプール内にあります。ノード i はノード next[i] につながっており、-1 でリストが終了します。リストAはノード headA から始まり、リストBはノード headB から始まります。ノードは特定の順序で格納されているわけではないため、リンクをたどってください。
2つのリストは途中で合流する場合があります。あるノード以降、末尾まで同じノードをたどります。両方のリストに含まれる最初のノードのインデックスを返してください。共有するノードがない場合は -1 を返してください。
関数
- nextinteger-array
- 各ノードがリンクしているノードのインデックス、またはリストの最後のノードの場合は -1
- headAinteger
- リストAの最初のノード
- headBinteger
- リストBの最初のノード
- 戻り値integer
- 2つのリストが共有する最初のノード、または -1
制約
2 ≤ n ≤ 104。ここで、nはnextの長さです。- 各
next[i]は-1または0からn-1までのノードインデックスです。 0 ≤ headA, headB ≤ n-1かつheadA ≠ headB。- どちらのリストも、ノードを2回訪れることなく
-1で終わります。サイクルはありません。 - すべてのノードは、リスト A、リスト B、またはその両方にあります。
例
- 入力
- next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
- 出力
- 1
- 説明
- Aは
3, 5, 1, 4, 0を訪れ、Bは2, 1, 4, 0を訪れます。ノード1以降はすべてのノードを共有し、それより前のAのノードはB上にないため、答えは1です。
- 入力
- next = [2, 3, 4, -1, -1]headA = 0headB = 1
- 出力
- -1
- 説明
- リストAは
0, 2, 4で、リストBは1, 3です。共通のノードに触れることなく、どちらも-1で終わるため、答えは-1です。
- 入力
- next = [3, 2, 0, -1]headA = 1headB = 0
- 出力
- 0
- 説明
- リストAは
1, 2, 0, 3で、リストBは0, 3です。リストBはリストAの末尾なので、最初に共有されるノードはheadBそのもの、ノード0です。
発展問題
追加メモリ O(1) で、O(m + k) 時間でノードを見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ノードは
nextを1つ持っています。2つのリストが同じノードに到達したら、再び分岐することはあるでしょうか？このことから、2つのリストの形について何がわかりますか？両方のリストの長さが同じなら、並んでたどり、2つのポインターが同じノードに立ったところで止められます。問題は、長いリストの先頭に余分なノードがあることです。両方のポインターが同じ距離を進むには、どうすればよいでしょうか？
ポインター
aをリスト A に沿って進め、末尾を越えたらheadBから再開します。bについても同様に、headAから再開します。a == bになったら停止します。そのノード、または-1が答えです。
解説
ノードはnextを1つ持つため、一度合流した2つのリストが再び分岐することはありません。2つの独立した開始点が共有の末尾につながったYの形になり、その合流点が答えです。開始点までの長さは異なる場合があるため、両方のリストを同時に進めても合流点を見つけられません。以下では、mとkはそれぞれAとBの長さです。
Aの各ノードをBのすべてのノードと照合する
正しいが、最大のテストでは終わらない
考え方
ポインターはノードのインデックスで、次に進むには node = next[node] とします。A の各ノード a を順番に調べ、B のすべてのノードをたどって、各ノードを a と比較します。一致する最初の a が答えです。それより前の A のノードはすべて一致しなかったからです。A のノードごとに B を再スキャンします。各リストに 5000 個のノードがあり、共有ノードがない場合、比較回数は 2.5 × 10^7 回になります。
アルゴリズム
a = headAを設定します。aが-1でない間、headBから-1までbをたどります。- 途中で
b == aになったら、aを返します。 - そうでなければ、
a = next[a]に移動して繰り返します。 - リスト A の終端に達したら、
-1を返します。
def getIntersectionNode(next, headA, headB):
a = headA
while a != -1:
# Is node a also on list B? Walk all of B to find out.
b = headB
while b != -1:
if a == b:
return a
b = next[b]
a = next[a]
return -1リストBのノードに印を付ける
考え方
各ノードについて「このノードはB上にあるか」を一度ずつ確認します。Bをたどり、サイズnのブール配列で各ノードに印を付けます。ノードのインデックスは小さな整数なので、配列でハッシュセットの代わりになります。次に、Aを先頭からたどります。最初に印が付いているノードは両方のリストに含まれており、Aを順番にたどるため、それが該当する最初のノードです。最初の例では、Bの2, 1, 4, 0に印が付き、Aをたどると3と5を通過してから1で停止します。各リストを一度ずつたどるので、n個の印を付ける代わりに、時間計算量はO(m + k)です。
アルゴリズム
n個のブール値をすべて false に設定した配列onBを作成します。headBからリスト B をたどり、各ノードについてonB[node] = trueに設定します。headAからリスト A をたどります。onB[node]が true である最初のノードを返します。- リスト A の末尾に到達した場合は、
-1を返します。
def getIntersectionNode(next, headA, headB):
# Mark every node of list B.
on_b = [False] * len(next)
node = headB
while node != -1:
on_b[node] = True
node = next[node]
# The first marked node on list A is the meeting point.
node = headA
while node != -1:
if on_b[node]:
return node
node = next[node]
return -1リストを切り替える2つのポインター
考え方
各リストを接合点で分けます。Aはプライベートノードx個の後に共有ノードc個が続き、Bはプライベートノードy個の後に同じc個が続きます。ポインターaはAを進み、-1に移動してからheadBで再スタートし、x + c + 1 + y回移動した後、2回目に接合点に到達します。ポインターbはBを進んでからAを進み、y + c + 1 + x回移動した後に到達します。合計は一致します。最初の例ではx = 2、y = 1、c = 3で、どちらも7回移動した後にノード1に位置します。
共有する末尾がない場合、両方のポインターはm + 1 + k回移動した後に-1に位置します（m = kの場合はm回移動した後です）。ループは-1を返します。各ポインターが切り替える前に-1に移動するのは、この共通の停止位置があるためです。各ポインターの移動回数は最大m + k + 1回で、メモリはインデックス2つ分です。
アルゴリズム
a = headA、b = headBを設定します。a != bの間、aが-1ならheadBに、そうでなければnext[a]に移動します。- 同じラウンドで、
bが-1ならheadAに、そうでなければnext[b]に移動します。 - ループが終了したら、
aを返します。これは最初に共有されているノード、または-1です。
def getIntersectionNode(next, headA, headB):
a, b = headA, headB
# Each pointer walks its own list, then the other one. Both cover
# the same number of nodes, so they reach the meeting node together,
# or reach -1 together when there is none.
while a != b:
a = headB if a == -1 else next[a]
b = headA if b == -1 else next[b]
return a
落とし穴と境界ケース
- 最後のノードからもう一方のヘッドへ直接切り替え、
-1で停止するのを省略する。リストに共通の要素がない場合、ポインターが同じ値を持つことはなく、ループが永遠に実行される。 - ポインターをそれぞれ自身のヘッドから再開する。すると各ポインターは自身のリストを周回し、周回が揃ったときにだけ出会うため、最大で
(m + 1)·(k + 1)回の移動が必要になることがある。 - 配列の順序をリストの順序として扱う。ノード
0がヘッドなのは、headAまたはheadBがそう示している場合に限られ、配列内で隣り合う要素がリスト内でも隣り合うとは限らない。 - LuaとRでは、配列が1から始まることを忘れない。ノードのインデックスは0始まりのままにして、
next[node + 1]を読み取る。
よくある質問3
追加のメモリを使わずに、2つの連結リストが交差する位置を見つけるにはどうすればよいですか？
2つのポインターを動かします。それぞれが自分のリストを進み、末尾を過ぎたら、もう一方のリストの先頭から進み続けます。両方が同じ合計距離を進むため、最初に共有するノードに同時に到達するか、共有ノードがない場合は一緒に末尾に到達します。
リストの長さを比較して、共通部分を見つけられますか？
はい。両方のリストのノード数を数え、長い方のリストのポインターを差分だけ先に進めます。次に、両方を一度に1ステップずつ進めて、同じになるまで続けます。これも時間計算量は O(m + k)、メモリ計算量は O(1) です。切り替え方式なら、2回のカウント処理をせずに同じ位置合わせができます。
2つの連結リストの交差を見つける時間計算量はどれくらいですか？
2つのポインターと長さを使う方法は、O(m + k)時間で実行でき、追加メモリはO(1)です。一方のリストをセットまたはマーク配列に記録する方法も線形時間ですが、そのリストを保存するためのメモリが必要です。すべてのノードの組み合わせを比較すると、O(m·k)かかります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def getIntersectionNode(next, headA, headB):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next = [-1, 4, 1, 5, 0, 1] headA = 3 headB = 2
期待される出力
1