LeetCode-61.旋轉鏈表.md

題目描述：

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

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

示例 2:

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

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

我的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)鏈表力图，然后再找準旋轉后應該切割的位置即可步绸。那么如何找到最后該切割的位置呢，經過觀察和計算得出吃媒，假設當前元素的位置為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都會指向同一片內存空間a
head = head.next跋涣； // head指向的內存空間發(fā)生改變，但temp還是指向原來的內存空間a

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

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

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者