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;
    }
    
}