leetcode 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 * 10^9

分析：由于链表的长度可能小于k，而旋转链表长度的整数倍后链表会恢复原状，因此首先需要遍历一遍链表，统计链表长度len，同时记录链表的尾节点，通过k % len得到真正有效的旋转次数，避免重复旋转。之后将原链表的尾节点指向头节点，使链表首尾相连形成一个环。因为旋转后的链表本质上从原链表的某个位置断开，并重新选取一个新的头节点。因此，只需要找到新的头节点和新的尾节点，然后断开环即可完成旋转。

对于向右旋转k个位置，新的头节点应该是原链表中从头节点开始数第len - k个位置之后的节点。用dis = (len - k) % len表示从原头节点出发需要移动的步数。随后从head开始向后移动dis步，移动结束后，指针p指向新的头节点，指针q指向新的尾节点。

最后，将新的尾节点q的next指针置为空，断开之前形成的环，并返回新的头节点p。这样，原链表后面的k个节点就被移动到了链表前面，完成了链表的右旋操作。

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* rotateRight(struct ListNode* head, int k) { if(!k||head==NULL)return head; int len=0,dis=0; struct ListNode* p=head,*q=NULL; while(p!=NULL) { q=p,len++,p=p->next; } q->next=head,k=k%len,dis=(len-k)%len,p=head; for(int i=0;i<dis;++i) { q=p,p=p->next; } q->next=NULL; return p; }