LeetCode-61.旋转链表.md

题目描述：

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的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);
};

解题思路：

首先我想到的是将链表置为一个循环链表，然后再找准旋转后应该切割的位置即可。那么如何找到最后该切割的位置呢，经过观察和计算得出，假设当前元素的位置为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的链表返回的都是原链表

那么如何将链表置为循环链表呢？遍历到最后一个链表元素，然后将最后一个元素next指向头元素即可。我首先被js地址引用给迷惑住了，总是觉得将head赋值给一个temp临时元素之后，再循环遍历链表时需要将head = head.next ,我一开始认为这种操作会改变temp的值，但仔细分析发现不会

let temp = head;  // temp和head都会指向同一片内存空间a
head = head.next； // head指向的内存空间发生改变，但temp还是指向原来的内存空间a

let temp = head；
head.value = 'newValue' //这种情况才会改变temp的值

关于位置的计算：一开始写了个函数calPos，从前往后遍历数字，找到符合条件的索引，然后再遍历切割循环链表，但这种写法会超市。后来发现在切割循环链表时，也相当于对每一个位置进行了一次判断，因此消除了calPos位置函数。