題目描述：

給定一個鏈表，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向右移動 k 個位置，其中 k 是非負數(shù)。 示例 1:

輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

示例 2:

輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 2->0->1->NULL
向右旋轉(zhuǎn) 2 步: 1->2->0->NULL
向右旋轉(zhuǎn) 3 步: 0->1->2->NULL
向右旋轉(zhuǎn) 4 步: 2->0->1->NULL

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/rotate-list 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

我的AC代碼

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var traverse = function(head) {
    if (!head) {
        return {
            len: 0,
            head: null
        }
    }
    let len = 0;
    let secend = head.next;
    len++;
    if (!secend) {
        return {
            len: 1,
            head
        }
    }
    while(secend.next) {
        len++;
        secend = secend.next;
    }
    secend.next = head;
    return {
        len: len + 1,
        head: head
    };
}

/* var calPos = function(k, len) {
    for(let i = 0; i < len ; i++) {
        if ((i+k+1) % len === 0) {
            return i;
        }
    }
} */

var splitCircle = function (head, k, len) {
    let i = 0;
    while(head){
        if ((i+k+1) % len === 0) {
            res = head.next;
            head.next = null;
            return res;
        }
        head = head.next;
        i++;
    }
}

var rotateRight = function(head, k) {
    var {len, head} = traverse(head, k);
    if (len === 0 || len === 1) {
        return head;
    }
    return splitCircle(head, k, len);
};

解題思路：

首先我想到的是將鏈表置為一個循環(huán)鏈表，然后再找準旋轉(zhuǎn)后應(yīng)該切割的位置即可。那么如何找到最后該切割的位置呢，經(jīng)過觀察和計算得出，假設(shè)當前元素的位置為i，那么假如i+k+1 能被鏈表的長度len整除，那么這個元素就是鏈表最后的切割位置。舉個例子，對于示例1: 1->2->3->4->5->NULL, k = 2， 鏈表長度len為5， 2+1+2 可以被5整除，那么位置2即為最后要分割的位置，位置2（索引2）的元素為3，因此最后的鏈表是4->5->1->2>3->null.

還要注意特殊的邊界條件，空鏈表和長度為1的鏈表返回的都是原鏈表

那么如何將鏈表置為循環(huán)鏈表呢？ 遍歷到最后一個鏈表元素，然后將最后一個元素next指向頭元素即可。 我首先被js地址引用給迷惑住了，總是覺得將head賦值給一個temp臨時元素之后，再循環(huán)遍歷鏈表時需要將head = head.next ,我一開始認為這種操作會改變temp的值，但仔細分析發(fā)現(xiàn)不會

let temp = head;  // temp和head都會指向同一片內(nèi)存空間a
head = head.next； // head指向的內(nèi)存空間發(fā)生改變，但temp還是指向原來的內(nèi)存空間a

let temp = head；
head.value = 'newValue' //這種情況才會改變temp的值

關(guān)于位置的計算： 一開始寫了個函數(shù)calPos，從前往后遍歷數(shù)字，找到符合條件的索引，然后再遍歷切割循環(huán)鏈表，但這種寫法會超市。后來發(fā)現(xiàn)在切割循環(huán)鏈表時，也相當于對每一個位置進行了一次判斷，因此消除了calPos位置函數(shù)。