LeetCoding Challenge Oct. 7: Rotate List

2020/10/07に公開

LeetCode October Challenge の 7 日目。

今日の問題は Rotate List

問題の概要

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

考え方

  • 昨日の問題 と同様で大学の講義 (略)
  • この手の問題は愚直に解くのが良さげ
  • 今回の解法
    • まずはリストの先頭から末尾までを舐めて、リストの長さ len と最後のノードの参照 tail を求める
      • klen 以上とならないように 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;
    }
}

Discussion