LeetCoding Challenge Oct. 13: Sort List

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);
    }
}