検索ガイド -Search Guide-

単語と単語を空白で区切ることで AND 検索になります。
例: python デコレータ ('python' と 'デコレータ' 両方を含む記事を検索します)
単語の前に '-' を付けることで NOT 検索になります。
例: python -デコレータ ('python' は含むが 'デコレータ' は含まない記事を検索します)
" (ダブルクオート) で語句を囲むことで 完全一致検索になります。
例: "python data" 実装 ('python data' と '実装' 両方を含む記事を検索します。'python data 実装' の検索とは異なります。)
python_coding_challenge

Python coding challenge - linked list の右端から n 番目のノードを削除しよう! 投稿一覧へ戻る

Published 2022年7月25日6:42 by mootaro23

SUPPORT UKRAINE

- Your indifference to the act of cruelty can thrive rogue nations like Russia -

Python Coding Challenge - How will you remove the nᵗʰ node from the right?
(Python コーディングチャレンジ [linked list の右端から n 番目のノードを削除しよう!] 編)

与えられた linked list の右端から n 番目 (右端のノードが 1、その左隣りが 2, 3...) のノードを削除する方法を考えます。
問題:
linked list と int 値 n が与えられます。この時、linked list の右端から n 番目のノードを削除した linked list を返すプログラムを記述してください。linked list の右端のノードを 1、その左隣のノードを 2、その左隣りを 3... とします。
n が 0 や linked list のノード数よりも大きな数字である場合は与えられた linked list をそのまま返すこととします。また、ノード数が 1 の linked list と n も 1 が与えられた場合 linked list が消滅しますから None を返します。
例 1:
Linked list: 1 -> 2 -> 3 -> 4 -> 5
n: 3

# 出力: 1 -> 2 -> 4 -> 5
例 1 の解説:
与えられた linked list の右端から 3 番目のノードは 3 ですからこれを削除した linked list を返します。
例 2:
Linked list: 1 -> 2 -> 3 -> 4 -> 5
n: 6

# 出力: 1 -> 2 -> 3 -> 4 -> 5
例 2 の解説:
与えられた linked list の右端から 6 番目のノードは存在しません。与えられた linked list そのままを返します。
例 3:
Linked list: 1
n: 1

# 出力: None
例 3 の解説:
与えられた linked list の右端から 1 番目のノードは 1 です。これを削除すると linked list 自体が消滅しますから None を返します。
1つのノードを表現するクラスは以下の定義を利用します:
from typing import Any, Optional


class ListNode:

def __init__(self, data: Any, next: Optional['ListNode'] = None):
self.data = data
self.next = next
テスト用の linked list を作成する場合などに、通常のリストから連結リストを手軽に作成するために以下のヘルパー関数を利用することができます:
def make_linked_list_from_list(arr: list[Any]) -> ListNode:
head = ListNode(arr[0])
cur = head
for i in range(1, len(arr)):
temp = ListNode(arr[i])
cur.next = temp
cur = cur.next
return head
Linked list を文字列として出力するために以下のヘルパー関数を利用することができます:
def make_linked_list_str(root: ListNode) -> str:
res = []
while root:
res.append(str(root.data))
root = root.next
return ' -> '.join(res)
また関数定義は以下のような形です (同じである必要はありません):
def remove_n_th_from_end(head: ListNode, n: int) -> ListNode:
...
作成したプログラムは以下のテストをパスする必要があります:
import unittest


class TestRemoveNFromEnd(unittest.TestCase):

def test_1(self): # 無意味なノード番号(0) -> そのままの linked list が返される
head = make_linked_list_from_list([1])
res = remove_n_th_from_end(head, 0)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1')

def test_2(self): # 全てのノードがなくなる -> None が返される
head = make_linked_list_from_list([1])
res = remove_n_th_from_end(head, 1)
self.assertIsNone(res)

def test_3(self): # 無意味なノード番号(ノード数よりも多い) -> そのままの linked list が返される
head = make_linked_list_from_list([1])
res = remove_n_th_from_end(head, 2)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1')

def test_4(self): # 無意味なノード番号(0) -> そのままの linked list が返される
head = make_linked_list_from_list([1, 2, 3, 4, 5])
res = remove_n_th_from_end(head, 0)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 2 -> 3 -> 4 -> 5')

def test_5(self): # 無意味なノード番号(ノード数よりも多い) -> そのままの linked list が返される
head = make_linked_list_from_list([1, 2, 3, 4, 5])
res = remove_n_th_from_end(head, 6)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 2 -> 3 -> 4 -> 5')

def test_6(self): # 先頭ノードを削除
head = make_linked_list_from_list([1, 2, 3, 4, 5])
res = remove_n_th_from_end(head, 5)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '2 -> 3 -> 4 -> 5')

def test_7(self): # 中間ノードを削除
head = make_linked_list_from_list([1, 2, 3, 4, 5])
res = remove_n_th_from_end(head, 4)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 4 -> 5')

def test_8(self): # 中間ノードを削除
head = make_linked_list_from_list([1, 2, 3, 4, 5])
res = remove_n_th_from_end(head, 2)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 2 -> 3 -> 5')

def test_9(self): # 最終ノードを削除
head = make_linked_list_from_list([1, 2, 3, 4, 5])
res = remove_n_th_from_end(head, 1)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 2 -> 3 -> 4')


if __name__ == '__main__':
unittest.main()
考え方:
上の例 1 で考えます。与えられた linked list の右端から 3 番目のノード 3 を削除するには、ノード 2 の next 属性としてノード 4 をセットする必要があります。ですからノード 2、つまり linked list の右端から n+1 番目のノードを見つける必要がある、ということです。
しかし対象となっているのは singly linked list (単方向連結リスト) ですから、右端の位置も分からなければ、右端から n+1 番目のノードがどれなのか、を判断することもできません。
しかし2つのポインタを利用する sliding window technique を採用することでこの問題をスマートに解決することが可能です。つまり双方の間隔が n 開いている2つのポインタを利用することで、先行するポインタが None になる、すなわち linked list の右端を「通り過ぎた」時に、追いかけているポインタの位置は削除するノードの左側のノードに位置している、ということになります。
あとはこのノードの next 属性を変更するだけです。
ただし問題にも記載した通り、n の値が linked list の範囲内に収まっていない場合や、ノード数が 1 つの linked list の場合にその唯一のノードを削除した場合、といったような例外もちゃんと処理する必要があります。
linked list の右端から n 番目のノードを削除するプログラム実装例:
def remove_n_th_from_end(head: ListNode, n: int) -> ListNode:
if n < 1:
return head

cur = head
remove_prev = head

# ct が増加してから if cur is None: の判断をしていることに注意してください
# つまり cur が None になった後でも ct が 1 つ増加します
# これによって「先頭ノードの削除」の場合の判断が ct == n になります
for ct in range(n + 1):
if cur is None:
if ct == n: # 先頭ノードの削除が指定された
return head.next
return head # ノード数よりも大きい n が指定された
cur = cur.next

while cur:
cur = cur.next
remove_prev = remove_prev.next
remove_prev.next = remove_prev.next.next
return head
Complexity Analysis
(アルゴリズム解析 - 実行時間解析)
与えられる linked list のノード数を m とすると、先行するポインタは m 回のループを実行します。また追いかけるポインタは m - n 回のループを実行することになります。よってこのアルゴリズムの最悪計算時間は O(m) です。