Rotate List

 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         if(k<=0||head==NULL||head->next==NULL) return head;
13         ListNode prehead(0);
14         prehead.next=head;
15         ListNode *p=head,*pre;
16         int length=0;
17         while(p)
18         {
19             length++;
20             pre=p;
21             p=p->next;
22             
23         }
24         k=k%length;
25         k=length-k;
26         while(--k)
27         {
28             head=head->next;
29         }
30         
31         pre->next=prehead.next;
32         prehead.next=head->next;
33         head->next=NULL;
34         return prehead.next;
35     }
36 };

下面是参考网上比较聪明的做法，利用环

 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         if(k<=0||head==NULL||head->next==NULL) return head;
13         ListNode prehead(0);
14         prehead.next=head;
15         ListNode *p=head;
16         int length=0;
17         while(p->next)
18         {
19             length++;
20             p=p->next;
21             
22         }
23         length++;
24         k=k%length;
25         k=length-k;
26       p->next=head;
27         while(k--)
28         {
29             p=p->next;
30         }
31         
32         prehead.next=p->next;
33         p->next=NULL;
34         
35         return prehead.next;
36     }
37 };