【アルゴリズム脳トレ】leetcode medium 143 reorder list

こんにちは

今回の学びは

・math.ceil使わずにn//2 if n%2==0 else n//2+1をつかったよ

・linked listの操作は配列記憶が吉かも。（前回19 remove nth from endとう問題でもつかえたろうから）

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

リンクリストの並べ替え問題

これ実際に30分で解けと言われると、結構実装ではまりそう。。。

しかもデバッガーが使えない状態でと考えると

シッカリ頭とペンで描くことが大事とみた。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　O(n)

実際の実装はこちら

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        1->2->3->4
        1, 4, 2, 3
        1->2->3->4->5
        1, 5, 2, 4, 3
        """
        curr = head
        sz = 0
        array = []
        while curr:
            sz += 1
            array.append(curr)
            curr = curr.next


        curr = head
        stop = sz//2 if sz % 2 == 0 else (sz//2)+1
        print("sz:%s, stop:%s" % (sz, stop))
        if sz == 1: return head
        for i in range(stop):
            print("i:%s" % i)
            left = array[i]
            right = array[sz-1-i]
            right.next = left.next
            left.next = right

        if sz % 2 == 0:
            if 0 <= stop < sz:
                array[stop].next = None
        else:
            if 0 <= stop < sz:
                array[stop-1].next = None

        return head

実装後です。timespace analysis (時間とスペースの分析）は　O(N)

以前、勉強した

・math.ceil使わずにn//2 if n%2==0 else n//2+1をつかったよ。(他事例rotate image)

をいきなり使いこなしたよ。good

まとめ

・math.ceil使わずにn//2 if n%2==0 else n//2+1をつかったよ

・linked listの操作は配列記憶が吉かも。（前回19 remove nth from endとう問題でもつかえたろうから）

以上です