題目

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

解題思路：

用一個(gè)指針p遍歷鏈表，另一個(gè)指針q指向p的下一個(gè)節(jié)點(diǎn)，然后用q往后遍歷，并用cnt計(jì)數(shù)，如果后面有p后面沒有k個(gè)元素則推出循環(huán)，如果p后面有k個(gè)元素，就用q將p后面的k-1節(jié)點(diǎn)取出來(lái)，放到p的前面，當(dāng)插入第一個(gè)k-1個(gè)節(jié)點(diǎn)時(shí)，將q放到head之前就行，可以用head來(lái)操作，之后的話，就必須用一個(gè)prev節(jié)點(diǎn)來(lái)定位q要插入的位置，開始prev指向p的前面的指針，q就插入到p的前面，prev的后面，之后，q就插入到prev的后面。

代碼：

public ListNode reverseKGroup(ListNode head, int k) {  
        if (head == null)  
            return null;  
        if (k == 1)  
            return head;  
        ListNode last = new ListNode(0);  
        last.next = head;  
        head=last;  
        while (last.next != null) {  
            ListNode p1 = last.next;  
            int count = 1;  
            while (count < k && p1.next != null) {  
                p1 = p1.next;  
                count++;  
            }  
            if (count == k) {  
                p1 = last.next;  
                ListNode p0 = p1;  
                ListNode p2 = p1.next;  
                while (count-- > 1) {  
                    ListNode tmp = p2.next;  
                    p2.next = p1;  
                    p1 = p2;  
                    p2 = tmp;  
                }  
                last.next = p1;  
                p0.next = p2;  
                last = p0;  
            } else {  
                break;  
            }  
        }  
        return head.next;  
    }  

參考鏈接：

http://www.shangxueba.com/jingyan/1819445.html
http://blog.csdn.net/tingmei/article/details/8050556