🦁

LeetCoding Challenge Oct. 13: Sort List

2020/10/13に公開約3,500字

LeetCode October Challenge の 13 日目。

今日の問題は Sort List

問題の概要

  • 与えられた連結リストを値の昇順にソートする
    • 時間計算量 O(n * log(n)), 空間計算量 O(1) を達成できるかな?

考え方

  • 連結リストのソートとなると、クイックソートみたいなのは 🙅‍♀️ ですね
    • 時間計算量を考慮しても、このケースではマージソートを選択するのが正解だね
  • マージソートの実装は再帰を用いるのが常套手段ではあるけど、スタックフレームの消費も空間計算量に含めるとなると O(log(n)) になってしまう…
    • ここは徹底的に、定数オーダーの空間計算量で達成してみよう 💪
  • そういうわけで、再帰は使わずにマージソートを実装するよ!
  • ナイーブなアルゴリズムを考えてみると、こんな感じかしら?
    1. step = 1 から始める
    2. リストを step の長さごとに分解する
    3. 隣り合った 2 つのリストをマージする
    4. リストの末尾まで処理したら、step を 2 倍にして 2. 以降の処理を繰り返す
  • ざっと実装してみたが、ちょっと冗長なコードになってしまった… まあいいか… 😇
  • ひとまず submit → 一発で accept 👍
    • Runtime 6ms で Your runtime beats 41.43 % of java submissions. かあ… こんなものかねえ…
  • Runtime 6ms 以下の他の人の submit (サンプリング) を見てみたけど、みんな再帰を使ってるじゃん……
    • ぱっと見で同じコードにみえるけど、runtime が 3ms だったり 6ms だったして、この違いはなんだろうなあ…

コード

class Solution {
    static class MergeResult {
        final ListNode head;
        final ListNode tail;

        MergeResult(ListNode head, ListNode tail) {
            this.head = head;
            this.tail = tail;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        int length = lengthOf(head);
        for (int step = 1; step < length; step *= 2) {
            head = mergeSort(head, step);
        }

        return head;
    }

    int lengthOf(ListNode node) {
        int count = 0;
        while (node != null) {
            node = node.next;
            count++;
        }
        return count;
    }

    ListNode mergeSort(ListNode head, int step) {
        ListNode node = head;
        ListNode newHead = null, last = null;

        while (node != null) {
            ListNode head1 = node;
            ListNode head2 = node = skipAndUnlink(node, step);
            if (node == null) {
                if (last != null) {
                    last.next = head1;
                }
                break;
            }
            node = skipAndUnlink(node, step);

            MergeResult result = merge(head1, head2);
            if (newHead == null) {
                newHead = result.head;
            }
            if (last != null) {
                last.next = result.head;
            }
            last = result.tail;
        }

        return newHead;
    }

    ListNode skipAndUnlink(ListNode node, int step) {
        ListNode last = null;
        for (int i = 0; i < step && node != null; i++) {
            last = node;
            node = node.next;
        }
        if (last != null) {
            last.next = null;
        }

        return node;
    }

    MergeResult merge(ListNode head1, ListNode head2) {
        ListNode node1 = head1;
        ListNode node2 = head2;
        ListNode head = null, last = null;

        while (node1 != null && node2 != null) {
            ListNode next;
            if (node1.val <= node2.val) {
                next = node1;
                node1 = node1.next;
            } else {
                next = node2;
                node2 = node2.next;
            }

            if (head == null) {
                head = last = next;
            } else {
                last.next = next;
                last = next;
            }
        }

        assert last != null;

        last.next = node1 != null ? node1 : node2;
        while (last.next != null) {
            last = last.next;
        }

        return new MergeResult(head, last);
    }
}

Discussion

ログインするとコメントできます