1. 题目
原题链接
给你一个链表的头节点 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 * 109
Related Topics 链表 双指针
👍 576 👎 0
2. 题解
2.1 解法1: 闭合为环
算法流程:
1.同解法1 先计算链表长度, 同时找到尾节点
2.将链表闭合为环, 然后只要找到新的头结点及其前驱结点断链即可, 其头结点为 从 head 开始的第 len-k-1 个结点
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
int len = 1;
ListNode p = head;
while (p.next != null) {
len++;
p = p.next;
}
k = k % len;
if (k == 0) return head;
p.next = head;
int index = len - k;
p = head;
while (index > 1) {
index--;
p = p.next;
}
ListNode newHead = p.next;
p.next = null;
return newHead;
}
}
参考: 官方题解
2.2 解法2: 转化为寻找倒数第 k 个结点
参考链接: 算法—LeetCode 剑指 Offer 22. 链表中倒数第k个节点
算法流程:
- 因为 k 可能大于 n, 所以需要先求得链表长度 len, 用于取 k%len
- 寻找到链表倒数第 k 个结点(使用快慢指针), 该节点即为 新的头结点
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// 1. 求链表长度
ListNode p = head;
int len = 0;
while (p != null) {
len++;
p = p.next;
}
k = k % len;
if (k == 0) {
return head;
}
// 2. 寻找倒数第k个结点, 快慢指针, fast 先走 k 步, 然后 fast和 slow 一起走
ListNode fast = head;
ListNode slow = head;
while (k > 0) {
fast = fast.next;
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 此时 slow.next 为新的头结点
ListNode newHead = slow.next;
slow.next = null;
fast.next = head;
return newHead;
}
}
参考: 【负雪明烛】问题拆分,分享详细思路与代码注释