【leetcode 61】回転チェーンテーブルJava問題解

1562 ワード

leetcode分類の下ですべての問題解は作者本人が比較した後に選んだ問題解であり、読みやすく、メンテナンス性に優れている.
問題ごとに1つの答えしかなく、煩雑で実用的でない案を避けるため、必ずしも最適解とは限らない.
チェーンテーブルを指定し、チェーンテーブルを回転させ、チェーンテーブルの各ノードをk個の位置に右に移動させ、kは負ではない.
例1:
  : 1->2->3->4->5->NULL, k = 2
  : 4->5->1->2->3->NULL
  :
     1  : 5->1->2->3->4->NULL
     2  : 4->5->1->2->3->NULL

例2:
  : 0->1->2->NULL, k = 4
  : 2->0->1->NULL
  :
     1  : 2->0->1->NULL
     2  : 1->2->0->NULL
     3  : 0->1->2->NULL
     4  : 2->0->1->NULL
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//1
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        int i = 0;
        while(fast.next != null)
        {
            fast = fast.next;
            i++;
        }
        for(int j = i - k % i; j > 0; j--)
            slow = slow.next;
        fast.next = dummy.next;
        dummy.next = slow.next; //4 5 1 2 3        4   
        slow.next = null;
        return dummy.next;
    }
}

考え方:
  • は、j=k%i
  • ではなく、j=i-k%iであることに注意する.
  • fastは最後まで歩き、slowは回転後の最初のノードまで歩き、ポインタの指向
  • を回転させる.