Description

Given a list, rotate the list to the right by kplaces, where _k _is non-negative.

Example

Given 1->2->3->4->5and k =2, return 4->5->1->2->3.

Solution

注意corner case: k > length, k = k%length; k == length, return HEAD.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param head: the List
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    public ListNode rotateRight(ListNode head, int k) {
        // write your code here
        if (head == null || k < 0) {
            return head;
        }

        k = k % getLength(head);

        if (k == 0) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

       fast.next = dummy.next;
       ListNode next = slow.next;
       slow.next = null;
       return next;
    }

    private int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }

        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }

        return len;
    }
}