61. Rotate List

Leetcode link

解题思路

题目要求我们给一个链表旋转 k 个位置，而且把 k 的范围给了一个 ，所以考虑优化肯定需要取余。

回到解题思路本身，链表旋转本质上就是三个步骤：

1. 把原来链表的 “尾巴” 接到 “ 头” 上
2. 确定新的链表头
3. 把新链表头的前一个链表的 next指定为NULL

具体落实到代码里，考虑细节的话需要做到如下几步：

1. 计算链表长度，并把链表尾接到链表头上
2. 计算新的链表头的位置
3. 留一个指针指向新链表的尾巴，并将其next置为NULL

C++

class Solution {
 public:
  ListNode* rotateRight(ListNode* head, int k) {
    if (head == NULL || k == 0) return head;
    int len = 1;
    ListNode* cur = head;
    // 计算链表长度，并把链表尾接到链表头上
    while (cur->next) {
      len++;
      cur = cur->next;
    }
    cur->next = head;

    cur = head;
    // 计算新的链表头的位置
    int step = len - (k % len);
    while (--step > 0) {
      cur = cur->next;
    }
    head = cur->next;

    // 将新链表尾置为NULL
    cur->next = NULL;

    return head;
  }
};

Javascript

var rotateRight = function (head, k) {
    if (!head || k === 0) return head;
    let len = 1;
    let cur = head;
    // 计算链表长度，并把链表尾接到链表头上
    while (cur.next) {
        len++;
        cur = cur.next;
    }
    cur.next = head;

    cur = head;
    // 计算新的链表头的位置
    let step = len - (k % len);
    while (--step > 0) {
        cur = cur.next;
    }
    head = cur.next;

    // 将新链表尾置为NULL
    cur.next = null;

    return head;
};