連結リストを反転する
3つのポインターをつなぎ替える反復処理と再帰処理で単方向連結リストを反転し、ホワイトボード風の図で各手順を追跡します。
「連結リストを反転する」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
リストの反転が不可欠な理由
連結リストの反転は、コーディング面接で最も頻繁に出題される問題の 1 つです。ノードを見失わずにポインターを正確に操作する能力が試されます。回文の検出、リストの再配置、k グループごとの反転など、大きなアルゴリズムの一部として登場するほか、単独の問題としても出題されます。
反復的な方法では、prev、curr、next_node の 3 つのポインターを使います。再帰的な方法では、同じ処理をコールスタックによる走査として表現します。どちらも O(n) 時間で実行でき、反復的な方法では O(1) 空間で実現できます。
3 ポインターによる反復的な反転
反復的に反転する各ステップでは、まずリストの残りを失わないように curr.next を保存し、curr.next を prev に向けて逆向きに変更し、prev を curr へ進め、curr を保存した次のノードへ進めます。curr が None になるとループが終了し、prev が新しい先頭になります。
覚え方は、保存、反転、前進、前進です。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.nextステップごとのトレース
1 -> 2 -> 3 に対して reverse_list をトレースします。初期状態は prev=None, curr=1 です。ステップ1：next=2 を保存し、1.next=None に反転して、prev=1、curr=2 とします。ステップ2：next=3 を保存し、2.next=1 に反転して、prev=2、curr=3 とします。ステップ3：next=None を保存し、3.next=2 に反転して、prev=3、curr=None とします。ループが終了したら、prev=3 を返します。これは 3 -> 2 -> 1 の新しい先頭です。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_traced(head):
prev, curr = None, head
step = 0
while curr:
step += 1
next_node = curr.next
curr.next = prev
print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
prev = curr
curr = next_node
return prev
nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val) # 3再帰による反転
再帰的な方法では、reverse_list(head.next) がすでに反転された後続部分の新しい先頭を返すと考えます。残る処理は、head と head.next の間のポインタを反転することだけです。head.next.next = head（元の2番目のノードから元の1番目のノードへ戻るようにする）を設定し、head.next = None（元の順方向のリンクを切断する）を設定します。新しい先頭はベースケースから上へ返されます。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_rec(head):
# Base case: empty or single node
if not head or not head.next:
return head
new_head = reverse_list_rec(head.next) # reverse suffix
head.next.next = head # former second node points back
head.next = None # sever forward link
return new_head
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
print(head.val, end=' ') # 4 3 2 1
head = head.nextサブリストの反転（LeetCode 92）
LeetCode 92 の「Reverse Linked List II」では、位置 left から right まで（1始まり）のサブリストを1回の走査で反転することが求められます。ポイントは、サブリストの直前のノードを見つけることです（ダミーの先頭を使えば、常にこのノードを有効に扱えます）。その後、3ポインタによる反転を (right - left) 回だけ実行し、最後に反転したセグメントをリストの前後につなぎ直します。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
dummy = ListNode(0, head)
pre = dummy
# Advance pre to node just before position 'left'
for _ in range(left - 1):
pre = pre.next
curr = pre.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = pre.next
pre.next = next_node
return dummy.next
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
print(head.val, end=' ') # 1 4 3 2 5
head = head.nextKグループ内のノードの反転（LeetCode 25）
LeetCode 25 の「Reverse Nodes in k-Group」では、連続する k 個のノードごとに反転します。手順は、まず k 個のノードが残っているか確認し、足りなければそのままにします。次の k 個のノードを反復的な方法で反転し、続いて残りのリストを再帰的に反転してつなぎます。時間計算量は O(n) のままで、再帰呼び出しの深さは O(n/k) です。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
# Check if k nodes are available
curr, count = head, 0
while curr and count < k:
curr = curr.next
count += 1
if count < k:
return head # fewer than k nodes left, keep as-is
# Reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now the tail of the reversed group
head.next = reverseKGroup(curr, k)
return prev
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
print(head.val, end=' ') # 2 1 4 3 5
head = head.next回文連結リスト
LeetCode 234 の「Palindrome Linked List」では、連結リストが回文かどうかを O(n) 時間、O(1) 空間で判定します。戦略は、スロー・ファストポインタで中央を見つけ、後半をその場で反転し、2つの半分をノードごとに比較して、必要に応じてリストを元に戻すことです。これは中央の探索と反転という、2つの基本的なスキルを組み合わせたものです。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
# Find mid
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def build(arr):
d = ListNode(0)
c = d
for v in arr:
c.next = ListNode(v)
c = c.next
return d.next
print(isPalindrome(build([1,2,2,1]))) # True
print(isPalindrome(build([1,2,3]))) # False反復版と再帰版の比較
反復的な反転は O(1) 空間 で実行でき、一般的にはこちらが推奨されます。再帰的な反転は呼び出しの深さにより O(n) のスタック領域 を使用するため、非常に長いリストではスタックオーバーフローが発生する可能性があります（Python のデフォルトの上限は約1000段階の再帰です）。
面接では、まず反復版を実装して空間計算量への意識を示し、その後、リストの長さに上限がある場合には、より簡潔な代替案として再帰版にも触れるとよいでしょう。
import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint
# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)反転でよくあるミス
反転のバグのほとんどは、次の3つのミスが原因です。1つ目は、next を上書きする前に保存しないことです。next_node を保存していない状態で curr.next = prev を実行すると、前方への参照が失われます。2つ目は、prev を返さないことです。ループの終了時には curr が None になっていますが、prev が新しい先頭です。3つ目は、再帰のベースケースを誤ることです。not head.next を忘れると、1ノードだけのリストを処理できず、AttributeError が発生します。
# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # BUG if omitted: lose rest of list
curr.next = prev
prev = curr
curr = next_node
return prev # BUG if you return curr: it is None
nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
print(h.val, end=' ') # 3 2 1
h = h.nextリストの再配置（LeetCode 143）
LeetCode 143 の「Reorder List」では、L0 → L1 → L2 → ... → Ln を L0 → Ln → L1 → Ln-1 → L2 → Ln-2 の形に O(n) 時間、O(1) 空間で並べ替えます。解法は、中央を見つける、後半を反転する、2つの半分を交互に組み合わせるという3つの手順を組み合わせたものです。反転を身につけると、一見複雑なこの問題も、慣れ親しんだ手法を組み合わせるだけの明快な問題になります。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Find mid
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Interleave
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
print(h.val, end=' ') # 1 4 2 3
h = h.nextまとめ：反転は基本部品
連結リストの反転が最終的な目的になることはほとんどありません。これは基本部品です。回文の判定、kグループ反転、リストの再配置、指定位置間の反転は、いずれも同じ3ポインタによる反復パターンを利用します。このパターンを自動的に使えるようになれば、より高レベルな問題の構造に思考力を集中できます。
反転は、2分以内に記憶だけで書けるようになるまで、必ず練習してください。連結リストの面接では、ほぼ必ず何らかの形で登場します。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンの振り返り
このレッスンでは、反復的な Save-Flip-Advance-Advance パターンによって、リストを O(n) 時間、O(1) 空間で反転できること、再帰的な方法では後続部分がすでに反転されていると考え、最後のリンクだけを修正すること、そして反転が回文の判定、リストの再配置、kグループ反転における中核的な手順であることを学びました。次は Floyd のアルゴリズムによる循環検出を扱います。
よくある質問
「連結リストを反転する」レッスンは無料ですか？
はい。「連結リストを反転する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「連結リストを反転する」で何を学びますか？
3つのポインターをつなぎ替える反復処理と再帰処理で単方向連結リストを反転し、ホワイトボード風の図で各手順を追跡します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「連結リストを反転する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。