RSSフィードを購読
Python Coding Challenge - How will you remove the nᵗʰ node from the right?
(Python コーディングチャレンジ [linked list の右端から n 番目のノードを削除しよう！] 編)
(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
n: 3
# 出力: 1 -> 2 -> 4 -> 5
例 1 の解説:
与えられた linked list の右端から 3 番目のノードは 3 ですからこれを削除した linked list を返します。
例 2:
Linked list: 1 -> 2 -> 3 -> 4 -> 5
n: 6
n: 6
# 出力: 1 -> 2 -> 3 -> 4 -> 5
例 2 の解説:
与えられた linked list の右端から 6 番目のノードは存在しません。与えられた linked list そのままを返します。
例 3:
Linked list: 1
n: 1
n: 1
# 出力: None
例 3 の解説:
与えられた linked list の右端から 1 番目のノードは 1 です。これを削除すると linked list 自体が消滅しますから None を返します。
１つのノードを表現するクラスは以下の定義を利用します:
from typing import Any, Optional
class ListNode:
def __init__(self, data: Any, next: Optional['ListNode'] = None):
self.data = data
self.next = next
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
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)
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()
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 番目のノードがどれなのか、を判断することもできません。
しかし２つのポインタを利用する sliding window technique を採用することでこの問題をスマートに解決することが可能です。つまり双方の間隔が n 開いている２つのポインタを利用することで、先行するポインタが 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
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
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) です。