61. 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.

链接：https://leetcode.com/problems/rotate-list/#/description

4/26/2017

19ms， 35%

先找到链表的长度，并找到相对移动的k

用快指针找到距离差，用快慢指针一起找到新的head

注意

1. 判断nodeVisited之后还有判断k在模length之后是否为0，0的话可以直接返回

2. 第19行，fast应该重新回到head

 1 public class Solution {
 2     public ListNode rotateRight(ListNode head, int k) {
 3         if (head == null) return null;
 4         
 5         int length, nodeVisited = k;
 6         ListNode slow = head, fast = head;
 7 
 8         while (fast != null && nodeVisited > 0) {
 9             fast = fast.next;
10             nodeVisited--;
11         }
12         if (nodeVisited == 0 && fast == null) return head;
13         else if (nodeVisited > 0) {
14             length = k - nodeVisited;
15             k = k % length;            
16         }
17         if (k == 0) return head;
18         
19         fast = head;
20         while (k > 0) {
21             fast = fast.next;
22             k--;
23         }
24 
25         while (fast.next != null) {
26             slow = slow.next;
27             fast = fast.next;
28         }
29         ListNode temp = slow.next;
30         slow.next = null;
31         fast.next = head;
32         return temp;
33 
34     }
35 }

别人的算法：

变成环，然后再来找

https://discuss.leetcode.com/topic/14470/my-clean-c-code-quite-standard-find-tail-and-reconnect-the-list

 1 class Solution {
 2 public:
 3     ListNode* rotateRight(ListNode* head, int k) {
 4         if(!head) return head;
 5         
 6         int len=1; // number of nodes
 7         ListNode *newH, *tail;
 8         newH=tail=head;
 9         
10         while(tail->next)  // get the number of nodes in the list
11         {
12             tail = tail->next;
13             len++;
14         }
15         tail->next = head; // circle the link
16 
17         if(k %= len) 
18         {
19             for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)
20         }
21         newH = tail->next; 
22         tail->next = NULL;
23         return newH;
24     }
25 };