力扣每日一题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

通过次数

339.4K

提交次数

821.1K

通过率

41.3%

思路一、值交换

先遍历一次链表，将每个节点的地址放入一个指针数组，每个节点的值放入一个int数组，并记录长度n。因为链表每向后移动n个位置，又回到了起点，所以k先对n取余，减去不比较的重复操作。随后再遍历一次链表，将位置为i的值改为位置为（i+n-k)%n 的值。

//值交换
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(head==NULL) return head;if(k==0) return head;ListNode *ptr[501];int a[501];int n=0;//节点数ListNode *p=head;while(p!=NULL){a[n]=p->val;ptr[n]=p;p=p->next;n++;}k=k%n;int i=0;for(i=0;i<n;i++){int index=(i+n-k)%n;ptr[i]->val=a[index];}return head;}
};

思路二、闭合为环，头结点向后移动n-k%n次即可。

将链表首尾相接，头结点向后移动n-k%n次，再将head前面的指针断开，就达到了向后移动k个位置的效果。

//闭合为环
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(head==NULL||k==0||head->next==NULL) return head;int n=1;ListNode *p=head;while(p->next!=NULL){p=p->next;n++;}int add=n-k%n;if(add==n) return head;p->next=head;//首尾相连while(add--){head=head->next;p=p->next;}p->next=NULL;return head;}
};