25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked 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

解法1： O(N)

考点是基本的linkedlist操作，每次找出一个要反转的subList的头的前一个node和他的尾巴node,反转了之后再把新subList接回原来的list就可以了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {

        if (head == null) return null;
        if (k <= 1) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode tail = dummy;

        while (tail != null && tail.next != null) {

            int count = 0;
            // first find the end of the sub list
            ListNode subHead = tail;
            while (tail != null && count < k) {
                ++count;
                tail = tail.next;
            }

            // tail point to the end of the subList
            if (tail == null) break;

            ListNode next = tail.next;
            tail.next = null;

            ListNode subRealHead = subHead.next;
            ListNode temp = reverse(subRealHead);
            subHead.next = temp;    // connect the new head to front
            subRealHead.next = next;    // connect the new tail to end
            tail = subRealHead; // set tail to be the last element in the current subList
        }

        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }

        return prev;
    }
}