旋转链表

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

解答：使用双指针法 首先定义指针pos和int型变量size，遍历完之后pos指向链表的最后一个元素（NULL前面的那个元素），size即为链表的长度。 我们发现，假如k刚好是size的整数倍的话，其实链表旋转了k次之后，压根就没有变化（直接返回head即可），所以不管k是多少，链表旋转k次的结果，会和旋转k % size次相同。 定义一个cut指针指向head，当cut往后走size-move-1个单位之后，它后面的部分就是要断开的部分。 比如说，链表是a->b->c->d->e->f->g，k=3。那么会有：size=7、pos最终指向g、move=3和size-move-1=3。 最终链表应该是e->f->g->a->b->c->d，所以e->f->g是应该被断开的部分，然后接到a的前面。 于是乎，cut从head处往后走size-move-1个单位之后，会来到d，然后cut后面刚好就会是e->f->g。 让cut -> next = nullptr，就会把e->f->g从链表中断开。 这时候我们要做的只剩下把e->f->g接上a就大功告成了。在代码中，result就指向e，是需要最终链表的头节点，而一开始的pos大家别忘了，它指向g，就是初始链表的尾节点。 所以只需要写pos -> next = head，然后return result就可以了。

class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(!head||!head->next||k==0) return head; ListNode* pos = head; int size = 1, move = 0; while(pos&&pos->next){ pos = pos->next; size++; } move = k%size; if(move==0) return head; ListNode* cut = head; for(int i=0;i<size-move-1;++i){ cut = cut->next; } ListNode* result = cut->next; pos->next = head; cut->next = nullptr; return result; } };