旋转链表 (opens new window)

• 难度：Medium
• 标签：链表 环链表

刷题思路

• [x] 迭代
• [x] 环链表

方法 1 迭代

• 思路: 常规思路按照题意解题
  • 1. 计算链表长度，k%n得到右移位置个数减少冗余计算，长度减去右移个数得到"进到旋转中点所需步数"
  • 2. 加入哨兵头方便计算，得到旋转中点
  • 3. 开始旋转，哨兵接旋转中点后面部分，尾节点尾接断尾的head
• 复杂度：
  • 时间 O(N). 一趟遍历计算长度 O(N) + 一趟遍历找中点&找结尾 O(N)
  • 空间 O(1)

var rotateRight = function(head, k) {
    // 1) 计算链表长度，k%n得到右移位置个数减少冗余计算，长度减去右移个数得到旋转中点
    let len = 0
    let curr = head
    while (curr) [len, curr] = [len+1, curr.next]
    k = k % len
    let left = len - k // 推进到旋转中点所需步数
    // 2）加入哨兵头方便计算，得到旋转中点
    let newHead = new ListNode(null)
    newHead.next = head
    let mid = newHead
    for (let i=0; i<left; i++) mid = mid.next
    // 3) 开始旋转，
    let next = mid.next
    mid.next = null
    newHead.next = next
    curr = newHead
    while (curr.next) curr = curr.next
    curr.next = head
    return newHead.next
};

方法 2 环链表

• 思路: 如果链表最后一个节点尾接头链表头则可以形成环，由方法1可知，只需要找到起点作为头，在终点处断链即可:
  • 1. 形成环 & 计算链表长度;
  • 2. 计算所需推进步数;
  • 3. 推进得到起点，然后推进链表长度后断链
• 复杂度：
  • 时间 O(N). 遍历计算长度 O(N) + 计算起点 O(N) + 找到终点 O(N).
  • 空间 O(1)

var rotateRight = function(head, k) {
    if (!head || !head.next) return head
    // - 1) 形成环 & 计算链表长度;
    let [curr, len] = [head, 1]
    while (curr.next) [curr, len] = [curr.next, len+1]
    // - 2) 计算所需推进步数;
    let target = len - (k % len)
    // - 3) 推进得到起点，然后推进链表长度后断链
    curr.next = head
    let res = head
    for (let i=0; i<target; i++) res = res.next // 计算起点
    curr = res
    for (let i=1; i<len; i++) curr = curr.next // 计算终点前一位
    curr.next = null // 中断环状链表
    return res
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~