LeetCode-61.旋转链表

haiweilian2021-03-09算法LeetCode

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 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

示例 1：

输入: 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

解法一

如果要旋转得先构造成一个环，然后再找到新的头节点再断开这个环。

举例 1->2->3->4->5 移动 k = 1 位，结果为 5->1->2->3->4。

构成一个环的办法，循环链表获取未节点指向头节点，并获取链表的长度(size = 5)。成环后 1->2->3->4->5->1->2->3->4->5->...。
假设现在指针 H 默认指向 1，那么右旋转一步后，H 指针应该指向 5(可以拿表感受下)。
那么新的头节点的位置在 size - k => 5 - 1 = 4（右旋转，后面的就转上来了）。
如果我们要把 5 当头节点，那么必须断开这个环链表。断开链表必须从上一个节点断开那么需要往前找一个节点。size - k - 1 => 5 - 1 - 1 = 3。
但是如果当 k > size 好像就不是那么回事了，如 k = 6 套用公式为 5 - 6 - 1 = -2。其实当 k 是旋转链表长度的整数倍时，它和未旋转是一样的，所以可以对 k 取余数 6 % 5 = 1 相当于只走了一步。
所以得出的公式为 size - (k % size) - 1 套用公式得出 5 - (1 % 5) - 1 = 3。所以我们需要循环 3 次找到 4节点。
最后把 4 节点的下一个节点保存起来，再断开 4 节点和 5 节点得到以 5节点开头的链表。

代码实现

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
  if (!head || !head.next || !k) return head;

  let pre = head;
  let size = 1;

  // 获取链表的长度
  while (pre.next) {
    pre = pre.next;
    size++;
  }

  // 让链表的末位节点指向头节点构成一个环。
  // 这里的引用关系：因为最后的 pre.next 是对 head 最后一个的引用，所以现在 head 现在是一个从头开始的环。
  pre.next = head;

  // 顺时针旋转，所以要算出走几步才能到达新的头节点。
  // 当 K 比链表长度数值要大时，K 要对链表长度取余。因为当 K 是旋转链表长度的整数倍时，它和未旋转是一样的。
  let length = size - (k % size) - 1;
  for (let i = 0; i < length; i++) {
    head = head.next;
  }

  // 保存新的头节点 => 4.next = 5
  pre = head.next;

  // 断开头节点和上个节点的环 => 4 和 5 断开
  head.next = null;

  return pre;
};

// ===================================================================
// ========================== @test ==================================
// ===================================================================
let ListNode = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 5,
          next: null,
        },
      },
    },
  },
};

function print(head) {
  let cur = head;
  let link = [];
  while (cur) {
    link.push(cur.val);
    cur = cur.next;
  }
  return `长度为 ${link.length} : 值为 ${link.join("->")}`;
}

console.log(print(rotateRight(ListNode, 1))); // 长度为 5 : 值为 5->1->2->3->4

LeetCode-61.旋转链表

题目描述

解法一

ON THIS PAGE