网络异常,图片无法展示
|
题目描述
这是 LeetCode 上的 61. 旋转链表 ,难度为 中等。
Tag : 「链表」、[快慢指针]
给你一个链表的头节点 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] 复制代码
提示:
- 链表中节点的数目在范围 [0, 500] 内
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9109
快慢指针
本质还是道模拟题,分步骤处理即可:
- 避免不必要的旋转:与链表长度成整数倍的「旋转」都是没有意义的(旋转前后链表不变)
- 使用「快慢指针」找到倒数第 k 个节点(新头结点),然后完成基本的链接与断开与断开操作
代码(感谢 @Die Eule 同学提供的 cpp 和 js 版本):
class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || k == 0) return head; // 计算有效的 k 值:对于与链表长度成整数倍的「旋转」都是没有意义的(旋转前后链表不变) int tot = 0; ListNode tmp = head; while (tmp != null && ++tot > 0) tmp = tmp.next; k %= tot; if (k == 0) return head; // 使用「快慢指针」找到倒数第 k 个节点(新头结点):slow 会停在「新头结点」的「前一位」,也就是「新尾结点」 ListNode slow = head, fast = head; while (k-- > 0) fast = fast.next; while (fast.next != null) { slow = slow.next; fast = fast.next; } // 保存新头结点,并将新尾结点的 next 指针置空 ListNode nHead = slow.next; slow.next = null; // 将新链表的前半部分(原链表的后半部分)与原链表的头结点链接上 fast.next = head; return nHead; } } 复制代码
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(1)O(1)
闭合成环
另外一个做法是,先成环,再断开:
- 找到原链表的最后一个节点,将其与原链表的头结点相连(成环),并统计链表长度,更新有效 k 值
- 从原链表的头节点出发,找到需要断开的点,进行断开
代码:
class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || k == 0) return head; // 先将链表成环,并记录链表的长度 // tmp 会记录住原链表最后一位节点 int tot = 0; ListNode tmp = head; while (tmp.next != null && ++tot > 0) tmp = tmp.next; tot++; k %= tot; if (k == 0) return head; // 正式成环 tmp.next = head; // 从原链表 head 出发,走 tot - k - 1 步,找到「新尾结点」进行断开,并将其下一个节点作为新节点返回 k = tot - k - 1; while (k-- > 0) head = head.next; ListNode nHead = head.next; head.next = null; return nHead; } } 复制代码
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.61
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。