マージ、分割、末尾からN番目を探す
2つのソート済み連結リストをO(n)でマージし、slow-fastポインターで中央からリストを分割し、末尾からn番目のノードを見つけます。
「マージ、分割、末尾からN番目を探す」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
連結リストに不可欠な3つのパターン
このレッスンでは、より難しい問題の基本部品として頻繁に登場する、連結リストの3つの基本操作を扱います。2つのソート済みリストのマージ（マージソートや k-way マージで使用）、リストを中央で分割すること（マージソートや回文の判定で使用）、そして末尾から n 番目のノードを見つけること（末尾から n 番目のノードの削除で使用）です。
3つとも、すでに学んだ技法であるダミーの先頭ノード、スロー・ファストポインタ、そして境界の慎重な追跡を利用します。
2つのソート済みリストのマージ
LeetCode 21 の「Merge Two Sorted Lists」では、2つのソート済み連結リストを受け取り、1つのソート済みリストにマージして返します。ダミーの先頭と、末尾を指す curr ポインタを使います。各ステップで2つのリストの先頭を比較し、小さい方のノードを curr に接続します。一方のリストを使い切ったら、もう一方の残りを接続します。時間計算量は O(n+m)、空間計算量は O(1) です（その場でポインタをつなぎ替えます）。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))マージをステップごとにトレース
mergeTwoLists([1,2,4], [1,3,4]) をトレースします。1と1を比較し、l1(1)を選び、l1を2へ進めます。2と1を比較し、l2(1)を選び、l2を3へ進めます。2と3を比較し、l1(2)を選び、l1を4へ進めます。4と3を比較し、l2(3)を選び、l2を4へ進めます。4と4を比較し、l1(4)を選び、l1を None へ進めます。残りの l2(4) を接続します。結果は [1,1,2,3,4,4] です。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))スロー・ファストポインタで中央を見つける
リストを中央で分割するには、スロー・ファストポインタのパターンを使います。slow は1ステップ、fast は2ステップ進みます。fast が None（または最後のノード）に到達したとき、slow は中央に位置します。長さが偶数のリストでは、中央にある2つのノードのうち前のノードになります。これはマージソートでの分割における一般的な扱いです。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]連結リストのマージソート
LeetCode 148「リストのソート」：連結リストを O(n log n) 時間、O(log n) 空間でソートします。アプローチは、リストを中点で分割し、それぞれの半分を再帰的にソートしてからマージするというものです。連結リストでは中点での分割が O(n)（配列のように O(1) ではありません）ですが、全体の計算量は O(n log n) で、スタック領域も O(log n) しか必要としないため、連結リストにはマージソートが自然に適しています。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]末尾から N 番目のノードを見つける
LeetCode 19「リストの末尾から N 番目のノードを削除」：1回の走査で末尾から n 番目のノードを見つけます。ちょうど n 個分離した2つのポインタを使います。fast を slow より n ステップ先に進めます。その後、fast が最後のノードに到達するまで、両方を同時に進めます。この時点で slow は末尾から (n+1) 番目のノード、つまり削除対象ノードの直前のノードにあります。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Remove Nth における n+1 ステップの理由
重要なポイントは、ダミーヘッドから n ではなく n+1 ステップだけ fast を進めることです。n+1 ステップ後、どちらもダミーヘッドから開始しているため、fast は slow より n+1 個先にあります。fast が None に到達すると（末尾の1つ先）、slow は None の n+1 個前、つまりゼロ始まりで位置 (length - n - 1)、すなわち対象ノードの直前にあります。これにより、slow.next = slow.next.next で末尾から n 番目のノードを簡潔に削除できます。
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')2つの連結リストの交点
LeetCode 160「2つの連結リストの交点」：2つのリストが初めて交わるノードを見つけます。O(1) 空間で実現する方法は、各リストに1つずつポインタを進めることです。ポインタが None に到達したら、もう一方のリストの先頭に移します。最大 len(A) + len(B) ステップ後には、両方のポインタが同じ総距離を進んでいるため、交点ノードに到達します。交点がない場合は、両方とも None に到達します。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
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 # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8K 個のソート済みリストをマージ（分割統治）
LeetCode 23「K 個のソート済みリストをマージ」：k 個のソート済みリストが与えられたとき、それらを1つにマージします。最適なアプローチは、分割統治を使ってリストのペアを繰り返しマージし、各ラウンドでリストの数を半分にすることです。平均長 n のリストが k 個ある場合、計算量は O(n k log k) で、順番にマージする場合の O(n k²) より効率的です。min-heap を使う方法も O(n k log k) です。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]奇数・偶数連結リスト
LeetCode 328「奇数・偶数連結リスト」：すべての奇数番目のノードを先に並べ、その後に偶数番目のノードを並べます（1始まり）。2本の独立したチェーン（奇数用と偶数用）を維持し、最後に接続します。リストを1回走査するだけでよいため、計算量は O(n)、空間計算量は O(1) です。これは、異なる進み幅で2つのポインタを同時に進める方法の、分かりやすい例です。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]すべてを組み合わせる
このレッスンで扱った3つのパターン、つまりソート済みリストのマージ、中点での分割、末尾から n 番目の要素の検索には、追加のメモリを使わず、位置を追跡するために追加のポインタ変数を使うという共通点があります。ダミーヘッドはマージと削除を簡単にし、スロー・ファストポインタ間の間隔は特定の相対位置を固定します。また、一方のポインタを先に進めることで、必要な間隔を作ります。
面接では、コードを書く前に使用するパターンを説明してください。「1回の走査で末尾から n 番目を見つけるため、2ポインタの間隔テクニックを使います」と述べれば、構造的に考えていることを示せます。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、2つのソート済みリストのマージでは、ダミーヘッドと各ステップでの比較を使い、O(n+m) 時間、O(1) 空間で処理できること、中点での分割では、ファストポインタを最後の有効なペアで止めるスロー・ファストポインタを使うこと、そして末尾から n 番目の要素を見つけるには、ファストポインタを n+1 ステップ先に進めることで、スローポインタを直前のノードに置けることを学びました。次はスタックとキューを作り、典型的な面接問題に応用します。
AI チューターと学ぶ Python — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 30
- レッスン
- 120
よくある質問
「マージ、分割、末尾からN番目を探す」レッスンは無料ですか？
はい。「マージ、分割、末尾からN番目を探す」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「マージ、分割、末尾からN番目を探す」で何を学びますか？
2つのソート済み連結リストをO(n)でマージし、slow-fastポインターで中央からリストを分割し、末尾からn番目のノードを見つけます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「マージ、分割、末尾からN番目を探す」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Nodeクラスとリストの構築
- 連結リストを反転する
- Floydのアルゴリズムによる循環検出
- マージ、分割、末尾からN番目を探す