个人网站优秀作品谷歌 chrome 浏览器

力扣 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

思路分析 

最开始的时候我是尝试过截断法的，就是每旋转一次，就将后面的结点指向头结点并把前面的结点的指针截断置空，但后面调试发现，这只适用于旋转一次，因为旋转后，新的尾结点的前驱结点找不到了，就算实现了，时间复杂度O（n2）也挺高的。

后面我发现了一种思路，也是截断法，但不同的在于它是一次性截完，我们之前写过一题，找出链表的倒数第N个结点，比如说n=2，当我们找到了倒数第二个结点时，我们发现，该节点后面的所有结点不就是我们所需要旋转的结点吗，我们就没必要一个个截断，找到所有需要旋转的点一次性截断就行了。

关于快慢指针走的步数，题目给的值万一很大就会超出时间限制，其实我们之前写过关于字符串的旋转，当旋转次数等于字符串长度时，等于没旋转，记得将次数模一下链表长度再进循环。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* rotateRight(struct ListNode* head, int k) {struct ListNode* tail=head;//快指针struct ListNode* prev=head;//慢指针struct ListNode* cur=head;//记录链表长度int n=0;if(k==0||head==NULL||head->next==NULL){return head;}while(cur){n++;cur=cur->next;//计算链表长度}k=k%n;//记得模一下
//找需要截断的结点位置while(k--){if(tail->next==NULL){tail=head;}else{tail=tail->next;}}while(tail->next){tail=tail->next;prev=prev->next;}
//截断tail->next=head;//将末尾结点指向头结点head=prev->next;//头结点移动到prev的下一个成为新头节点prev->next=NULL;//截断prev和tail，prev成为链表尾结点return head;}