[LeetCode] Rotate List_综合

[Problem]

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.

[Analysis]
（1）虽然题目是进行旋转，但实际上可以看成是在链表中间断开，然后颠倒拼接，所以关键问题是找到断开点。
（2）对于k，旋转k次和旋转nk次是一样的效果，所以需要k %= length，如果k=0，则不需要操作。
（3）最后，还需要注意对head指针进行reset

[Solution]

// Definition for singly-linked list.
struct ListNode {
      
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

// Definition for Solution
class Solution {
      
public:
    ListNode *rotateRight(ListNode *head, int k) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        if(NULL == head){
      
            return NULL;
        }
       
        // get length
        int len = 0;
        ListNode *p = head;
        while(p != NULL){
      
            len++;
            p = p->next;
        }
   
        // reset k
        k %= len;
   
        // rotate
        if(k != 0){
      
            // get the last node
            p = head;
            int firstIndex = len - k;
            while(--firstIndex){
      
                p = p->next;
            }
   
            // reset the last node
            ListNode *first = p->next;
            p->next = NULL;
   
            // reset the head node
            p = first;
            while(p->next != NULL){
      
                p = p->next;
            }
            p->next = head;
            head = first;
        }
   
        return head;
    }
};