NeetCode 150 [Linked List]: medium: Reorder List

NeetCodeのSolutionを書いていく

Reorder List

問題

片方向リンクリストの先頭が与えられる。
長さ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. スローポインタとファストポインタでリストを半分に分割。
2. 後半のリストを逆転する
3. 前半のリストと交互にくっつければ回答となる

計算量は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