LeetCoding Challenge Oct. 7: Rotate List

LeetCode October Challenge の 7 日目。

今日の問題は Rotate List。

問題の概要

• 与えられた連結リストの要素を右に k 個ローテートした結果を返す

考え方

• 昨日の問題 と同様で大学の講義 (略)
• この手の問題は愚直に解くのが良さげ
• 今回の解法
  • まずはリストの先頭から末尾までを舐めて、リストの長さ len と最後のノードの参照 tail を求める
    • k が len 以上とならないように k を調整しておく
    • len - k 以降の要素がローテートされてリストの先頭に移動してくることになる
  • tail の次のノードとして head をつなぐことで、リストを一時的にリング状にする
  • 次に len - k - 1 番目のノードの参照を得る
    • このノードはリストの新たな末尾ノードとなり、さらにその次のノードがリストの新たな先頭ノードとなる
  • 同ノードとその次のリンクを切る
• submit → runtime 0ms 達成 🎉

コード

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode tail = null;
        int len = 0;
        for (ListNode node = head; node != null; node = node.next) {
            tail = node;
            len++;
        }

        k = len - (k % len);
        if (k == 0) {
            return head;
        }

        tail.next = head;

        for (ListNode node = head; k > 0; node = node.next) {
            tail = node;
            k--;
        }

        head = tail.next;
        tail.next = null;

        return head;
    }
}