RSSフィードを購読
Python Coding Challenge - How will you create odd and even linked lists?
(Python コーディングチャレンジ [linked list の奇数番目のノードを前半にまとめ、その後ろに偶数番目のノードを繋げよう！] 編)
(Python コーディングチャレンジ [linked list の奇数番目のノードを前半にまとめ、その後ろに偶数番目のノードを繋げよう！] 編)
今回も懲りずに linked list を操作します。linked list マスターを目指しましょう！
問題：
Singly linked list (単方向連結リスト) が与えられます。この linked list の奇数番目のノードを前半に、偶数番目のノードを後半に連結した linked list を返すプログラムを記述してください。それぞれのノードの順番は元の linked list に登場する順番とします。また、与えられた linked list のポインタだけを操作して結果のリストを取得する必要があります。
例:
与えられる linked list: 2 -> 1 -> 3 -> 4 -> 6 -> 7 -> 10
# 出力: 2 -> 3 -> 6 -> 10 -> 1 -> 4 -> 7
解説:
与えられた linked list の奇数番目のノードは 2, 3, 6, 10、偶数番目のノードは 1, 4, 7 です。よって最終的に作成される linked list は、奇数番目を最初に、その後ろに偶数番目を繋げた 2 -> 3 -> 6 -> 10 -> 1 -> 4 -> 7 になります。
１つのノードを表現するクラスは以下の定義を利用します:
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 odd_even_list(head: ListNode) -> ListNode:
...
...
作成したプログラムは以下のテストをパスする必要があります:
import unittest
class TestOddEvenList(unittest.TestCase):
def test_1(self):
head = make_linked_list_from_list([1])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1')
def test_2(self):
head = make_linked_list_from_list([1, 2])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 2')
def test_3(self):
head = make_linked_list_from_list([1, 2, 3])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 2')
def test_4(self):
head = make_linked_list_from_list([1, 2, 3, 4])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 2 -> 4')
def test_5(self):
head = make_linked_list_from_list([1, 2, 3, 4, 5, 6, 7, 8])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> 8')
if __name__ == '__main__':
unittest.main()
class TestOddEvenList(unittest.TestCase):
def test_1(self):
head = make_linked_list_from_list([1])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1')
def test_2(self):
head = make_linked_list_from_list([1, 2])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 2')
def test_3(self):
head = make_linked_list_from_list([1, 2, 3])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 2')
def test_4(self):
head = make_linked_list_from_list([1, 2, 3, 4])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 2 -> 4')
def test_5(self):
head = make_linked_list_from_list([1, 2, 3, 4, 5, 6, 7, 8])
res = odd_even_list(head)
res_str = make_linked_list_str(res)
self.assertEqual(res_str, '1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> 8')
if __name__ == '__main__':
unittest.main()
考え方:
与えられた linked list の先頭 (1 番目 = 奇数番目) から始めて１つ飛ばしに奇数番目のノードを辿っていくポインタと、先頭ノードの next (2 番目 = 偶数番目) から始めて１つ飛ばしに偶数番目のノード辿っていくポインタの２つを利用します。勿論、それぞれの先頭ノードを保存しておかなければいけません。
プログラムの先頭で、与えられた linked list が存在することを確認しておくことが必要です。そうすることで奇数番目のノードが１つは必ず存在することが保証されます。
偶数番目のノードが存在し、かつ、そのノードの next ノードも存在する限りループします。プログラムの先頭で「必ず１つは奇数番目のノードが存在する」ことが確認できていますし、このループの条件として「偶数番目のノードの next ノードも存在する == 次の奇数番目のノードが存在する」ことを検証していますから、ループを続ける条件として「奇数番目のノードが存在するか」という判断は必要ない、ということになります。
ループの中ではそれぞれのポインタを進めていくことになります。次の奇数番目のノードは偶数番目のノードの next 属性のノードですし、その次の偶数番目のノードはその「移動後」の奇数番目のノードの next 属性のノードです。
そして、このループを抜けてきた、ということは、どちらかのポインタの next 属性の値が None になった、ということです。つまり、奇数番目ポインタの next が None かもしれないし、偶数番目ポインタの next が None かもしれません。しかしどちらにせよ、奇数番目ポインタの next に偶数番目リストの先頭ノードをセットすれば、前半部分には奇数番目ノード、後半部分には偶数番目ノードのリストが連結された linked list が取得できる、ということになります。
linked list の奇数番目のノードを前半に、その後ろに偶数番目のノードを繋げるプログラム実装例：
def odd_even_list(head: ListNode) -> ListNode:
if not head:
return head
odd_cur = head
even_first = odd_cur.next
even_cur = even_first
while even_cur and even_cur.next:
odd_cur.next = even_cur.next
odd_cur = odd_cur.next
even_cur.next = odd_cur.next
even_cur = even_cur.next
odd_cur.next = even_first
return head
if not head:
return head
odd_cur = head
even_first = odd_cur.next
even_cur = even_first
while even_cur and even_cur.next:
odd_cur.next = even_cur.next
odd_cur = odd_cur.next
even_cur.next = odd_cur.next
even_cur = even_cur.next
odd_cur.next = even_first
return head
Complexity Analysis
(アルゴリズム解析 - 実行時間解析)
リストの最初から最後までループ処理しますので最悪計算時間は O(n) です。