61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example: Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) return head;

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

        k = len - k % len;
        if(k == len) return head;
        ListNode rTail = head;
        while(k-- > 1){
            rTail = rTail.next;
        }
        ListNode newHead = rTail.next;
        rTail.next = null;
        tail.next = head;

        return newHead;


    }
}

There is another smart yet simpler solution. after find the last node, link last node to the head, then move forward len - k%len step, you will reach the new tail, break the cycle from there, then you find the new head.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) return head;

        int len = 0;
        ListNode tail = head;
        while(tail.next != null){
            len++;
            tail = tail.next;
        }
        len++;
        k = len - k % len;
        if(k == len) return head;
        tail.next = head;

        while(k-- >0){
            tail = tail.next;
        }
        head =tail.next;
        tail.next = null;
        return head;

    }
}