61. Rotate List

https://leetcode.com/problems/rotate-list/description/

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

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

　　

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

在看答案之前 自己想了想 大致想法是对的

只是没有想到用环 这个solution很棒！

/**

* 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) {
        //k%length(listnode) 就是向前挪几个 
        //fist walk the list and get its length n, save the tail pre_pointer->tail_pre_pointer
        //then compute num = k % n(tail num should be move to the head)
        //index_key = n - num (from n - num to the last n-1 should be move to the head just in order)
        //find the pre_pointer of index_key -> key_pre_pointer
        //tail_pointer->next->next = head_pointer->next,head_pointer = ,key_pre_pointer->next = null key_pre_pointer。。。晕了
        // （以上是自己想法，没有想到用环，下面代码是最佳solution，用到了首尾相连的环 在这种不需要改变前后顺序的题目里面很适合用环 只改变首尾）


        if(!head) return head;

        int len=1; // number of nodes
        ListNode *newH, *tail;
        newH=tail=head;

        while(tail->next) // get the number of nodes in the list
        {
        tail = tail->next;
        len++;
        }
        tail->next = head; // circle the link

        if(k %= len) 
        {
        for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)
        }
        newH = tail->next; 
        tail->next = NULL;
        return newH;
    } 
};

https://leetcode.com/problems/rotate-list/discuss/22735/My-clean-C++-code-quite-standard-(find-tail-and-reconnect-the-list)