闭合为环
解题思路
定义一个哨兵节点 dmg 指向 head ，迭代链表将 head 和尾部连接起来形成一个圆环，并获取链表的长度；
dmg 向后移动
Math.abs((k % len) - len)，如果k > len需要获得k % len旋转了几次，再减去 len 才是 dmg 需要移动的步数；断开圆环，返回断开后的头节点
复杂度
-
时间复杂度：
O(n)，最坏情况下，需要遍历该链表两次； -
空间复杂度：
O(1)
代码实现
var rotateRight = function (head, k) {
if (!head) return head;
// 1. 定义一个哨兵节点指向 **head** ，迭代链表将 **head** 和尾部连接起来形成一个圆环，并获取链表的长度；
let dmg = new ListNode(0, head)
let tail = head;
let len = 1;
while (tail && tail.next) {
tail = tail.next;
len++;
}
tail.next = dmg.next;
// 2. dmg 向后移动
let count = Math.abs((k % len) - len);
while (count--) {
dmg = dmg.next
}
// 3. 断开圆环，返回断开后的头节点
let h = dmg.next;
dmg.next = null;
return h;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 328. 奇偶链表
上一篇
评论
