您现在的位置是:首页 >技术教程 >【刷题之路Ⅱ】LeetCode 61. 旋转链表网站首页技术教程
【刷题之路Ⅱ】LeetCode 61. 旋转链表
【刷题之路Ⅱ】LeetCode 61. 旋转链表
一、题目描述
原题连接: 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]
提示:
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
二、解题
1、方法1——移动部分链表
1.1、思路分析
由题目给出的示例中我们不难看出,“将链表每个节点向右移动 k 个位置。”,其实就等同于将将从链表倒数第k个节点之后的链表翻转到链表的前面:
所以我们就可以先找到链表的第k个节点和尾节点,然后将这部分链表接到链表的前面即可,但因为是单链表,所以我们实际还要找到的其实是链表的倒数第k + 1个节点(也就是倒数第k个节点的前一个节点)。
例如上面的例子中,我们想旋转两次:
如上图,当pre指针指向倒第三个节点tial,cur指向倒数第二个节点并且tial指针指向尾节点后,我们就可以先将pre的next置空,然后再让tail的next指向头节点,然后再将头指针指向cur的下一个节点即可:
而当k等于链表的长度是,其效果就等同于根本没有翻转,所以当k大于或等于链表的长度时候,设链表的长度为len,那么其效果就等同于翻转了k mod len个节点,所以我们就可以先算出链表的长度len,然后执行k %= len,若执行后k等于0,那我们就不用翻转直接返回head即可。
关于找链表的倒数第k个节点,我们可以沿用[LeetCode 剑指 Offer 22. 链表中倒数第k个节点]中节点的快慢指针的解法。
初始时,我们让一个快指针fast和一个慢指针slow同时指向链表的头节点,然后我们可以先让快指针向前走k - 1步:
然后我们让快慢指针同步往后走,当快指针走到链表的尾节点时,慢指针就指向了链表的倒数第k个节点:
同时我们还需要同时记录slow的前一个节点,以完成上述的操作。
1.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
struct ListNode* rotateRight(struct ListNode* head, int k){
if (NULL == head || NULL == head->next) {
// 如果链表为空或是只有一个节点,那我们就不用翻转了
return head;
}
struct ListNode *cur = head;
// 先算出链表的长度
int len = 0;
while (cur) {
len++;
cur = cur->next;
}
k %= len;
if (k == 0) {
return head;
}
// 找到链表的倒数第k个节点
struct ListNode *fast = head;
struct ListNode *slow = head;
struct ListNode *pre = head; // 记录slow的前一个节点,初始化为head
while (--k > 0) {
fast = fast->next;
}
while (fast->next) {
fast = fast->next;
pre = slow;
slow = slow->next;
}
// 此时的slow就是倒数第k个节点,fast就是尾节点
pre->next = NULL;
fast->next = head;
head = slow;
return head;
}
时间复杂度:O(n),n为链表的长度。
空间复杂度:O(1),我们只需要常数级的额外空间。
2、方法1——闭合为环
2.1、思路分析
还有一个更加巧妙的方法就是先将链表闭合为环,然后在链表的的倒数第k + 1节点处断开即可:
我们让一个指针breakNode指向链表的倒数第k + 1个节点,然后再次处断开即可:
2.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
struct ListNode* rotateRight(struct ListNode* head, int k){
if (NULL == head || NULL == head->next) {
return head;
}
struct ListNode *cur = head;
struct ListNode *tail = NULL; // 记录链表的的尾节点,进行闭合成环
// 先算出链表的长度
int len = 0;
while (cur) {
len++;
tail = cur;
cur = cur->next;
}
k %= len;
if (k == 0) {
return head;
}
// 闭合成环
tail->next = head;
// 再找到链表的倒数第k+1个节点(倒数从1开始数起)
struct ListNode *breakNode = NULL;
cur = head;
int len2 = 0;
while (cur) {
len2++;
if (len2 == len - k) {
breakNode = cur;
break;
}
cur = cur->next;
}
// 在breakNode节点处断开
head = breakNode->next;
breakNode->next = NULL;
return head;
}
时间复杂度:O(n),n为链表的长度。
空间复杂度:O(1),我们只需要常数级的额外空间。