力扣刷题6——旋转链表——[快慢双指针法]
- 一、博客声明
- 二、题目描述
- 三、解题思路
- 1、思路说明
- 2、知识补充
- a、求链表的长度
- 四、解题代码(附注释)
一、博客声明
找工作逃不过刷题,为了更好的督促自己学习以及理解力扣大佬们的解题思路,开辟这个系列来记录。代码可能不是自己写的,不求方法最好,只求更多地理解大佬们的解题思路。
二、题目描述
给你一个链表的头节点 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
三、解题思路
1、思路说明
这个题目采用双指针来解题。首先我们要知道的是,如果链表的长度length
如果小于等于1的话,无论旋转几次都是它本身,所以直接返回head
;当长度大于1的时候,每进行length
次旋转都会回到原本的样子,所以需要对旋转次数k
进行处理,真正有意义的旋转次数为k % length
次。我们用两个指针遍历链表,找到旋转一次后的新头和新尾,找到够改变其指向关系,就可以了。然后旋转相应的次数就可以了。具体看下面的图片。
2、知识补充
a、求链表的长度
没有什么技巧,就按照下面的代码套,无非就是根据需求改变一下返回类型,如果链表长度太长就用long long
类型。
//获取链表的长度
int getLength(struct ListNode* head){int count = 0;while(head){count++;head = head->next;}return count;
}
四、解题代码(附注释)
//获取链表的长度
int getLength(struct ListNode* head){int count = 0;while(head){count++;head = head->next;}return count;
}struct ListNode* rotateRight(struct ListNode* head, int k) {int lenght = getLength(head);//获取链表长度if(lenght <= 1){ //长度小于等于1,直接返回headreturn head;} else { //否则的话,可以处理一下K,K大于lenght,则许多翻转没有必要k = k % lenght;}struct ListNode* preHead = malloc(sizeof(struct ListNode));//建立一个检测头,一直指向链表头部preHead->val = 0;preHead->next = head;while(k--){//下面的代码就是找到尾巴变成新的头,倒数第一个变成新的尾巴struct ListNode* tail2newHead = preHead->next->next;struct ListNode* newTail = preHead->next;while(tail2newHead->next){//遍历链表tail2newHead = tail2newHead->next;newTail = newTail->next;}tail2newHead->next = preHead->next;//尾巴变成新的头newTail->next = NULL;//倒数第一个变成新的尾巴preHead->next = tail2newHead; //检测头指向新头}struct ListNode* result = preHead->next; //结果指向头free(preHead);//释放内存return result;}