网站服务器名字,做网站最好用的软件,网站开发意义,搜索词热度查询力扣 61 旋转链表
题目描述
给你一个链表的头节点 head #xff0c;旋转链表#xff0c;将链表每个节点向右移动 k 个位置。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], k 2
输出#xff1a;[4,5,1,2,3]示例 2#xff1a; 输入#xff1a;head [0,1,2], …力扣 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 1000 k 2 * 109 思路分析
最开始的时候我是尝试过截断法的就是每旋转一次就将后面的结点指向头结点并把前面的结点的指针截断置空但后面调试发现这只适用于旋转一次因为旋转后新的尾结点的前驱结点找不到了就算实现了时间复杂度On2也挺高的。
后面我发现了一种思路也是截断法但不同的在于它是一次性截完我们之前写过一题找出链表的倒数第N个结点比如说n2当我们找到了倒数第二个结点时我们发现该节点后面的所有结点不就是我们所需要旋转的结点吗我们就没必要一个个截断找到所有需要旋转的点一次性截断就行了。
关于快慢指针走的步数题目给的值万一很大就会超出时间限制其实我们之前写过关于字符串的旋转当旋转次数等于字符串长度时等于没旋转记得将次数模一下链表长度再进循环。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* rotateRight(struct ListNode* head, int k) {struct ListNode* tailhead;//快指针struct ListNode* prevhead;//慢指针struct ListNode* curhead;//记录链表长度int n0;if(k0||headNULL||head-nextNULL){return head;}while(cur){n;curcur-next;//计算链表长度}kk%n;//记得模一下
//找需要截断的结点位置while(k--){if(tail-nextNULL){tailhead;}else{tailtail-next;}}while(tail-next){tailtail-next;prevprev-next;}
//截断tail-nexthead;//将末尾结点指向头结点headprev-next;//头结点移动到prev的下一个成为新头节点prev-nextNULL;//截断prev和tailprev成为链表尾结点return head;}
