[Leetcode] Rotate list 旋转链表

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given1->2->3->4->5->NULLand k =2,
return4->5->1->2->3->NULL.

题意：给定链表，将其旋转到右边K个结点之后。（也得吐槽一下我的翻译）

思路：若结点为NULL或k==0，意味不必旋转，则直接返回head即可。最开始遇到的问题是，如何找到从右往左数第K个结点，即旋转后新的起点。想到的是用快慢指针，快指针先走k步，然后，快慢一起走，直到fast->next=NULL，此时，slow->next即为新的表头，然后将slow->next赋为NULL，连接旧链表的首尾即可。编译不通过。汗，没有考虑K的值大于结点的个数情况，那我就简单的以为，这种情况没法访问，直接返回就行，结果又过不了。所以上网找大神们，取余！k=k%L_{list ，}即旋转，不足list长度的部分，若k==0，则说明，不需要旋转。代码如下：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *rotateRight(ListNode *head, int k) 
12     {
13         if(head==NULL||k==0)    return head;
14 
15         ListNode *fast=head;
16         ListNode *slow=head;
17         int len(0); //链表长度
18         while(fast)
19         {
20             fast=fast->next;
21             len++;
22         }
23         k%=len;     //取余
24         if(k==0)    return head;
25 
26         fast=head;  //重新回到head
27         while(k-->0)
28         {
29             fast=fast->next;
30         }
31         while(fast->next)
32         {
33             fast=fast->next;
34             slow=slow->next;
35         }    
36         ListNode *newList=slow->next;
37 
38         slow->next=NULL;
39         fast->next=head;
40 
41         return newList;
42     }
43 };

还有一种只用一个指针的方法，详见Grandyang的博客。这里仅有代码

 1 class Solution {
 2 public:
 3     ListNode *rotateRight(ListNode *head, int k) {
 4         if (!head) return NULL;
 5         int n = 1;
 6         ListNode *cur = head;
 7         while (cur->next) {
 8             ++n;
 9             cur = cur->next;
10         }
11         cur->next = head;  //形成环
12         int m = n - k % n;
13         for (int i = 0; i < m; ++i) //寻找起始点的前结点
　　　　　　{
14             cur = cur->next;
15         }
16         ListNode *newhead = cur->next;
17         cur->next = NULL;
18         return newhead;
19     }
20 };

《编程珠玑》中提到翻手算法实现对字符串的反转，KeepThing_网友对其进行解释，详情见这里。