Rotate List leetcode java

タイトル:
 
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 .
 
問題:
この問題は主に問題の意味を理解して、k個のnodeを逆さまに数えて、それから終わりまで前の部分と調子を合わせて、その例は、4->5は前を持って来て、1->2->3は後ろを持って行きます.
いくつかの特殊:
kはリスト全体の長さより大きくてもよいので、このときk対lenを型抜きする
型抜き後に0をとると、rotateを使わずに直接戻ることになります
 
特殊な状況を処理したら、おなじみのfaster/slowerダブルポインタで解決すればいいです(このlinkedlistを見て、逆数のものを見て、条件反射しました)
まずfasterにステップ長をnにして、それからfasterとslowerは更にいっしょに歩いて、fasterを知っています.next=nullは、slowerがカウントする開始点の前の位置を指すことを示します.
だからnextは戻るnewheadです.保存してください.
そしてfaster.nextはheadに接続されていますnextはnullとして保存され、キューの最後になります.
これでリストをrotateに渡しました.
これは私が考えている解法で、もう一つはリスト全体をつなぎ、リングにして、切り分け点を見つけて切ればいいです.
 
解法1:
 
 1    
public ListNode rotateRight(ListNode head, 
int n) {
 2         
if(head==
null||head.next==
null||n==0)
 3             
return head;
 4         ListNode fast = head, slow = head,countlen = head;
 5         ListNode newhead = 
new ListNode(-1);
 6         
int len = 0;
 7         
 8         
while(countlen!=
null){
 9             len++;
10             countlen = countlen.next;
11         }
12         
13         n = n%len;
14         
if(n==0)
15             
return head;
16         
17         
for(
int i = 0; i < n; i++)
18             fast = fast.next;
19         
20         
while(fast.next!=
null){
21             slow = slow.next;
22             fast = fast.next;
23         }
24         
25         newhead = slow.next;
26         fast.next = head;
27         slow.next = 
null;
28         
29         
return newhead;
30     }
解法2:
 1 
public ListNode rotateRight(ListNode head, 
int n) {
 2 
 3     
if (head == 
null || n == 0)
 4         
return head;
 5     ListNode p = head;
 6     
int len = 1;
//
since p is already point to head
 7 
    
while (p.next != 
null) {
 8         len++;
 9         p = p.next;
10     }
11     p.next = head; 
//
form a loop
12 
    n = n % len;
13     
for (
int i = 0; i < len - n; i++) { 
14         p = p.next;
15     } 
//
now p points to the prev of the new head
16 
    head = p.next;
17     p.next = 
null;
18     
return head;
19 }
 Reference for 2: http://leetcodenotes.wordpress.com/2013/08/14/leetcode-rotate-list-%E6%8A%8A%E5%90%8Ek%E4%B8%AArotate%E5%88%B0list%E5%89%8D%E9%9D%A2%E5%8E%BB%EF%BC%8Ck%E5%8F%AF%E4%BB%A5%E8%B6%85%E8%BF%87list%E6%9C%AC%E8%BA%AB%E9%95%BF%E5%BA%A6/