题目来源于 LeetCode 第 61 号问题:旋转链表,难度为「中等」,根据CodeTop评论区爆料,字节一面出现过。
视频讲解地址:https://ke.algomooc.com/detail/p_6243bcc1e4b04e8d90291891/8
网站会员的小伙伴可以微信联系我,开通上述视频的权限。
一、题目描述
给你一个链表的头节点 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^9
原题地址:https://leetcode.cn/problems/rotate-list/
二、题目解析
1、首先遍历整个链表,求出链表的长度len
。
2、根据题目的提示,k
可能很大,远超链表的长度,这样就会导致一种情况,比如 k = 1000,len = 999,每个节点向右移动 1 个节点和向右移动 k = 1000 个节点结果一样,所以进行一个取模的操作可以节省大量的移动操作。
3、接下来设置两个指针 former、latter 均指向链表的头节点,这两个指针的目的是去寻找出旋转之前的尾节点位置、旋转成功之后的尾节点位置。
4、先让 former
指针先向前移动 k 次,此时,former
就和 latter
相距 k 个节点了。
5、接下来,让 former
、latter
同时向后移动,直到 former
来到了最后一个节点位置。
6、这个时候,从 head
到 latter
有 len – k 个节点,latter + 1 到 former 有 k 个节点。
7、也就意味着,latter + 1
这个节点是移动 k 个节点成功之后的头节点。
8、只需要返回 latter + 1
后面这个节点 newHead
,并且断开连接就行了。
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 旋转链表(LeetCode 61):https://leetcode.cn/problems/rotate-list/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// 边界条件判断
if( head == null) {
return head;
}
// 1、第一步先要计算出链表的长度来
int len = 0;
// 2、这里我们设置一个指针指向链表的头节点的位置
ListNode tempHead = head;
// 3、通过不断的移动 tempHead ,来获取链表的长度
while (tempHead != null) {
// tempHead 不断向后移动,直到为 null
tempHead = tempHead.next;
// 每次遍历一个新的节点,意味着链表长度新增 1
len++;
}
// 由于题目中的 k 会超过链表的长度,因此进行一个取余的操作
// 比如 k = 1000,len = 999
// 实际上就是将链表每个节点向右移动 1000 % 999 = 1 个位置就行了
// 因为链表中的每个节点移动 len 次会回到原位
k = k % len;
// 4、接下来设置两个指针指向链表的头节点
// 这两个指针的目的是去寻找出旋转之前的尾节点位置、旋转成功之后的尾节点位置
// former 指针
ListNode former = head;
// latter 指针
ListNode latter = head;
// former 指针先向前移动 k 次
for(int i = 0 ; i < k ; i++){
// former 不断向后移动
former = former.next;
}
// 这样 former 和 latter 就相差了 k 个节点
// 5、接下来,两个指针同时向后移动,直到 former 来到了最后一个节点位置
while(former.next != null){
// former 不断向后移动
former = former.next;
// latter 不断向后移动
latter = latter.next;
}
// 6、此时,former 指向了最后一个节点,需要将这个节点和原链表的头节点连接起来
former.next = head;
// 7、latter 指向的节点的【下一个节点】是倒数第 k 个节点,那就是旋转成功之后的头节点
ListNode newHead = latter.next;
// 8、断开链接,避免成环
latter.next = null;
// 9、返回 newHead
return newHead;
}
}
2、C++ 代码
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
// 边界条件判断
if( head == NULL) {
return head;
}
// 1、第一步先要计算出链表的长度来
int len = 0;
// 2、这里我们设置一个指针指向链表的头节点的位置
ListNode *tempHead = head;
// 3、通过不断的移动 tempHead ,来获取链表的长度
while (tempHead != NULL) {
// tempHead 不断向后移动,直到为 NULL
tempHead = tempHead->next;
// 每次遍历一个新的节点,意味着链表长度新增 1
len++;
}
// 由于题目中的 k 会超过链表的长度,因此进行一个取余的操作
// 比如 k = 1000,len = 999
// 实际上就是将链表每个节点向右移动 1000 % 999 = 1 个位置就行了
// 因为链表中的每个节点移动 len 次会回到原位
k = k % len;
// 4、接下来设置两个指针指向链表的头节点
// 这两个指针的目的是去寻找出旋转之前的尾节点位置、旋转成功之后的尾节点位置
// former 指针
ListNode *former = head;
// latter 指针
ListNode *latter = head;
// former 指针先向前移动 k 次
for(int i = 0 ; i < k ; i++){
// former 不断向后移动
former = former->next;
}
// 这样 former 和 latter 就相差了 k 个节点
// 5、接下来,两个指针同时向后移动,直到 former 来到了最后一个节点位置
while(former->next != NULL){
// former 不断向后移动
former = former->next;
// latter 不断向后移动
latter = latter->next;
}
// 6、此时,former 指向了最后一个节点,需要将这个节点和原链表的头节点连接起来
former->next = head;
// 7、latter 指向的节点的【下一个节点】是倒数第 k 个节点,那就是旋转成功之后的头节点
ListNode *newHead = latter->next;
// 8、断开链接,避免成环
latter->next = NULL;
// 9、返回 newHead
return newHead;
}
};
3、Python 代码
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 边界条件判断
if not head or k == 0 :
return head
# 1、第一步先要计算出链表的长度来
_len = 0
# 2、这里我们设置一个指针指向链表的头节点的位置
tempHead = head
# 3、通过不断的移动 tempHead ,来获取链表的长度
while tempHead :
# tempHead 不断向后移动,直到为 NULL
tempHead = tempHead.next
# 每次遍历一个新的节点,意味着链表长度新增 1
_len += 1
# 由于题目中的 k 会超过链表的长度,因此进行一个取余的操作
# 比如 k = 1000,len = 999
# 实际上就是将链表每个节点向右移动 1000 % 999 = 1 个位置就行了
# 因为链表中的每个节点移动 len 次会回到原位
k = k % _len
# 4、接下来设置两个指针指向链表的头节点
# 这两个指针的目的是去寻找出旋转之前的尾节点位置、旋转成功之后的尾节点位置
# former 指针
former = head
# latter 指针
latter = head
# former 指针先向前移动 k 次
for i in range(0 , k ) :
# former 不断向后移动
former = former.next
# 这样 former 和 latter 就相差了 k 个节点
# 5、接下来,两个指针同时向后移动,直到 former 来到了最后一个节点位置
while former.next :
# former 不断向后移动
former = former.next
# latter 不断向后移动
latter = latter.next
# 6、此时,former 指向了最后一个节点,需要将这个节点和原链表的头节点连接起来
former.next = head
# 7、latter 指向的节点的【下一个节点】是倒数第 k 个节点,那就是旋转成功之后的头节点
newHead = latter.next
# 8、断开链接,避免成环
latter.next = None
# 9、返回 newHead
return newHead
四、复杂度分析
时间复杂度: 链表一共被遍历两次,因此总的时间复杂度为O(n),n是链表的长度。
空间复杂度:O(1),我们只需要常数的空间存储若干变量。
五、最后
这是「画解 LeetCode 高频面试 400 题」系列,题目均来源于 LeetCode 原题,高频依据参考自 LeetCode 评论区、CodeTop、牛客网、CSDN博客、往期学员面试反馈,系列中的部分题目已经录制为视频讲解形式,文字版讲解会新增到算法训练营的课程中,同时发布在此公众号。
本题已经录制视频,提供动画讲解和逐行代码手写环节,算法训练营的同学可以在课程中观看。
在这个系列文章里面,除了每一篇都提供图片辅助理解之外,也提供 Java、C++、Python 的解题代码,并且每一行代码均提供详细的注释,你可以直接参考注释写出其他编程语言的代码。
为了方便大家收藏与阅读,文章同步发布了到我的个人网站:https://www.algomooc.com,大家可以搜索 LeetCode 题号进行阅读更多题解。