lintcode(450)K組翻轉連結清單

Description:

給你一個連結清單以及一個k,将這個連結清單從頭指針開始每k個翻轉一下。

連結清單元素個數不是k的倍數，最後剩餘的不用翻轉。

Explanation:

給對外連結表 

1->2->3->4->5

k = 

2

, 傳回 

2->1->4->3->5

k = 

3

, 傳回 

3->2->1->4->5

Solution:

首先判斷長度能否翻轉。如果能翻轉，依次将節點插入頭部，直至操作k次。然後遞歸處理。注意每次傳回的結果都是k個長度的子串，每次翻轉後都需要拼接。

1 -> 2 -> 3 -> 4 -> 5   pre=null;                 

|       |       

c     cn     

1 -> 2 -> 3 -> 4 -> 5                                  2 -> 1 -> null

|       |      |       

pre   c    cn

1 -> 2 -> 3 -> 4 -> 5                                  3 -> 2 -> 1 -> null

|       |      |       |

       pre   c     cn

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @param k an integer
     * @return a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // Write your code here
        if(k == 1) return head;
        if(head == null || head.next == null) return head;
        
        ListNode current = head;
        ListNode pre = null;
        ListNode cnext = null;
        ListNode res = null;
        
        if(len(head , k)){
            cnext = current.next;
            int count = k;
            while(count >= 1){
                count--;
                cnext = current.next;
                if(count == 0){
                    res = current;
                }
                current.next = pre;
                pre = current;
                current = cnext;
            }
        }else{
            return head;
        }
        
        ListNode last = res;
        while(last.next != null){
            last = last.next;
        }
        
        ListNode next =  reverseKGroup(cnext , k);
        last.next = next;
        
        return res;
        
    }
    
    public boolean len(ListNode head , int k){
        while(head != null){
            head = head.next;
            k--;
        }
        return k<=0?true:false;
    }
    
}