[LeetCode] Rotate List

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

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

思路一：首先将链表链接成循环链表,并得到链表长度count。计算k%n,再从头开始前进 count - k就是断开位置。

　　　　时间复杂度O(n),空间复杂度O(1)

 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 (head == NULL || k <= 0) return head;
13         ListNode *pter = head;
14         int count = 1;
15         while (pter->next != NULL) {
16             pter = pter->next;
17             ++count;
18         }
19         pter->next = head;
20         pter = pter->next;
21         k %= count;
22         for (int i = 1; i < count - k; ++i) { //找到旋转后头节点的前一个节点
23             pter = pter->next;
24         }
25         head = pter->next;
26         pter->next = NULL;
27         
28         return head;
29     }
30 };

思路二：使用两个指针

 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 (head == NULL || k <= 0) return head;
13         
14         ListNode *pfast = head;
15         for (int i = 0; i < k; ++i) { 
16             if (pfast->next != NULL) {
17                 pfast = pfast->next;
18             } else {
19                 pfast = head;
20             }
21         }
22         
23         ListNode *pslow = head; //指向新的头节点的前一个节点
24         while (pfast->next != NULL) {
25             pfast = pfast->next;
26             pslow = pslow->next;
27         }
28         pfast->next = head;
29         head = pslow->next;
30         pslow->next = NULL;
31         
32         return head;
33     }
34 };