Skip to main content

旋转链表

61. 旋转链表

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

示例 1:

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

示例 2:

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

代码

重点公式：

k 是 5 的整数倍：链表不会发生位置变化。
k 不是 5 的整数倍：实际移动位数是 k%5 的值。

move = length - (k % length)

const head = {
  'val':1,
  'next':{
    'val':2,
    'next':{
      'val':3,
      'next':{
        'val':4,
        'next':{
          'val':5,
          'next':undefined
        }
      }
    }
  }
}
const k =2

思路：

防御性
计算链表的长度
链表最后指向原链表首位，形成闭环
通过链表的长度,计算移动距离
- 公式：move = length - k%length
断开对应节点

// 闭合成环法
var rotateRight = function(head, k) {
  // 防御
  if(!head || !head.next || !k)return head

  let length = 1
  let node = head

  // 1. 计算链表的长度
  while(node.next){
    length ++
    node = node.next
  }

  // 2. 链表最后一位值的 nextnext 指向原链表首位数字，形成闭环
  node.next = head;

  // 3. 获取移动距离
  //  创建一个变量，接收从 k 处截断后的链表
  //  k 是 5 的整数倍：链表不会发生位置变化。
  //  k 不是 5 的整数倍：实际移动位数是 k%5 的值。
  //  假设 k = 2，则 move = 3 ，我们就会从 3 这里处截断，然后 3 的 next 指向 null 即可
  let move = length - k % length

  // 获取断开节点
  while(move){
    node = node.next
    move --
  }
  // 4. 断开对应节点
  let temp = node.next
  node.next = null

  return temp
};

console.log(rotateRight(head,k))

61. 旋转链表
代码