Rotate List

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. 

---------------------------- thinking -----------------------------------------
1. using two pointers to rotate for general case
edges cases : 1. list.size equals to k 2. list.size equals to n*k (I didn't consider this case) 3. when reculculate khead, cnt should be reset to 0

----------------------------- codes ------------------------------------------------
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (head == NULL || head->next == NULL || k == 0) {
            return head;
        }
        int cnt = 0;
        ListNode *khead = head;
        while(cnt < k && khead) {
            khead = khead->next;
            cnt++;
        }
        if (khead == NULL) {
            //bug here!!: we should consider if list.size == n * k instead of 1 * k
            k = k % cnt;
            if (k == 0) {
                return head;
            }
            khead = head;
            //bug here!! cnt should be reset to 0
            cnt = 0;
            while(cnt < k && khead) {
                khead = khead->next;
                cnt++;
            }             
        }
        ListNode *tail = head;
        while (khead->next) {
            khead = khead->next;
            tail = tail->next;
        }
        ListNode *result = tail->next;
        tail->next = NULL;
        khead->next = head;
        return result;
    }

};