Rotate List

Source

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

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

Java

/**
 * 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 n) {
        int len = 0;  
        ListNode cur = head;  
        while(cur!=null){  
            len++;  
            cur = cur.next;  
        }  

        if(len==0 || n%len==0) return head;  

        //if n>len, then find the mod of n.  
        n %= len;  

        //find the distance of two pointers  
        ListNode slow = head;  
        ListNode fast = head;  
        int len1 = 1;  

        while(len1<=n){  
            fast = fast.next;  
            len1++;  
        }  

        //walk both pointers forward until the fast pointer reach the end.  
        while(fast.next != null){  
            slow = slow.next;  
            fast = fast.next;  
        }  

        ListNode tmp = slow.next;  
        slow.next = null;  
        fast.next = head;  
        head=tmp;  

        return head;      
    }
}