NeetCodeのSolutionを書いていく #
Reorder List #
https://neetcode.io/problems/reorder-linked-list
neetcode.io
問題 #
片方向リンクリストの先頭が与えられる。
長さ7のリンクリスト位置は以下のように表現される
[0, 1, 2, 3, 4, 5, 6]
リンクリストを次の並びになるように並び替えます。
[0, 6, 1, 5, 2, 4, 3]
長さnのリストは通常以下の並びになります
[0, n-1, 1, n-2, 2, n-3, ...]
ノードの値を変更せずにノードの順番を変更する必要があります。
制約 #
- リンクリストの長さは1以上1000以下
- ノードの値は1以上1000以下
計算時間：O(n) メモリ：O(1)
例 #
Input: head = [2,4,6,8] Output: [2,8,4,6]
Input: head = [2,4,6,8,10] Output: [2,10,4,8,6]
メモ #
計算時間はO(n)でリンクリストの位置を変える。 リンクの位置を変えた時点で初期状態の位置ではなくなるのがポイントか？ メモリがO(1)なので初期状態を保存しておくこともできない。 独自クラスであり、インデックス参照もできない。
ヒントを見た。
- スローポインタとファストポインタでリストを半分に分割。
- 後半のリストを逆転する
- 前半のリストと交互にくっつければ回答となる
計算量は1でn/2、2でn/2、3でn/2で全体定期にはO(n) メモリは逆転したリストを保持しないといけないのでO(n)では？ 違うか、逆転時に一時的に一つtempに保持すればいいからO(1)か
実装してみたけどめちゃごちゃごちゃ。 解説の回答はとってもシンプル。 うーん、アルゴリズム整理するのむずい。
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
# 1. スローポインタとファストポインタでリストを半分に分割。
def divide(head: Optional[ListNode]):
middle = head
slow = head
fast = head
while slow and fast and fast.next:
if slow.next:
middle = slow.next
slow = slow.next
if fast and fast.next and fast.next.next:
fast = fast.next.next
else:
fast = None
return middle
middle = divide(head)
# 2. 後半のリストを逆転する
def reverseList(node, next_node, next_next_node):
if not next_node:
return node
next_node.next = node
node = next_node
next_node = next_next_node
next_next_node = None if not next_next_node else next_next_node.next
return reverseList(node, next_node, next_next_node)
next_node = None if not middle.next else middle.next
next_next_node = None if not middle.next or not middle.next.next else middle.next.next
after_half = reverseList(middle, next_node, next_next_node)
middle.next = None
# 3. 前半のリストと交互にくっつければ回答となる
node = head
while node and node.next:
temp_before = node.next
node.next = after_half
node = node.next
if node is None:
break
temp_after = after_half.next
node.next = temp_before if node.next != None else None
node = node.next
after_half = temp_after