Pengjielee's blog

题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1： 1 -> 2 -> 3 -> 4 -> 5

rotate 1: 5 -> 1 -> 2 -> 3 -> 4 rotate 2: 4 -> 5 -> 1 -> 2 -> 3

输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]

示例 2： 0 -> 1 -> 2

rotate 1: 2 -> 1 -> 0 rotate 2: 1 -> 2 -> 0 rotate 3: 0 -> 1 -> 2 rotate 4: 2 -> 0 -> 1

输入：head = [0,1,2], k = 4 输出：[2,0,1]

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/rotate-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

将链表中每个节点向右移动K个位置，也就是将链表中倒数第K个节点作为头节点，其前面的所有节点放在原链表尾节点之后。

因此整体思路就是找到倒数第K个节点的前一个节点，然后让链表首尾相连，第K个节点作为链表旋转后的新的头节点，其前一个节点作为链表旋转后的尾节点。

作者：hardcore-aryabhata 链接：https://leetcode-cn.com/problems/rotate-list/solution/dong-hua-yan-shi-kuai-man-zhi-zhen-61-xu-7bp0/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
  if (head === null) {
    return head;
  }

  // 获取链表的长度
  const getLength = (head) => {
    let length = 0;
    while (head != null) {
      length++;
      head = head.next;
    }
    return length;
  };

  // 定义快指针
  let fast = head;
  // 定义快指针
  let slow = head;

  // 1 -> 2 -> 3
  // k = 1, 1%3=1, 3 -> 1 -> 2
  // k = 2, 2%3=2, 2 -> 3 -> 1
  // k = 3, 3%3=0, 1 -> 2 -> 3
  // k = 4, 4%3=1, 3 -> 1 -> 2

  const length = getLength(head);
  k = k % length;

  // 快指针先走k步
  for (let i = 0; i < k; i++) {
    fast = fast.next;
  }

  // 快慢指针一起走
  while (fast.next != null) {
    fast = fast.next;
    slow = slow.next;
  }
  // 快指针 指向 头节点，形成环
  fast.next = head;
  // 新的头节点即为慢指针的下个节点
  head = slow.next;
  // 慢指针的下个节点指向null，断开环
  slow.next = null;
  return head;
};