力扣挑战赛第13天-No.61旋转链表

题目描述

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

示例：

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

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

注意：

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

解法一

闭合成环

/**
 * 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}
 */
let rotateRight = function (head, k) {
  if (k === 0 || !head || !head.next) {
    return head;
  }
  let count = 1;
  let cur = head;
  while (cur.next) {
    count++;
    cur = cur.next;
  }
  let step = count - k % count;
  if (step === count) {
    return head;
  }
  cur.next = head;
  while (step) {
    cur = cur.next;
    step--;
  }
  let ret = cur.next;
  cur.next = null;
  return ret;
};

解法二

双指针（快慢指针）

/**
 * 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}
 */
let rotateRight = function (head, k) {
  if (k === 0 || !head || !head.next) {
    return head;
  }
  let count = 1;
  let cur = head;
  while (cur.next) {
    count++;
    cur = cur.next;
  }
  let rk = k % count;
  if (rk === 0) {
    return head;
  }
  let slow = head;
  let fast = head;
  while (rk > 0) {
    fast = fast.next;
    rk--;
  }
  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }
  let newHead = slow.next;
  slow.next = null;
  fast.next = head;
  return newHead;
};

Donate