LeetCode 实战：「图解」K 个一组翻转链表

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null || k <= 1) {
        return head;
    }

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

    while (pointer != null) {
        // 记录上一个子链表的尾
        ListNode lastGroup = pointer;

        int i = 0;            
        for (; i < k; ++i) {
            pointer = pointer.next;
            if (pointer == null) {
                break;
            }
        }

        // 如果当前子链表的节点数满足 k, 就进行反转
        // 反之，说明程序到尾了，节点数不够，不用反转
        if (i == k) {
            // 记录下一个子链表的头
            ListNode nextGroup = pointer.next;

            // 反转当前子链表，reverse 函数返回反转后子链表的头
            ListNode reversedList = reverse(lastGroup.next, nextGroup);

            // lastGroup 是上一个子链表的尾，其 next 指向当前反转子链表的头
            // 但是因为当前链表已经被反转，所以它指向的是反转后的链表的尾
            pointer = lastGroup.next;

            // 将上一个链表的尾连向反转后链表的头
            lastGroup.next = reversedList;

            // 当前反转后的链表的尾连向下一个子链表的头
            pointer.next = nextGroup;
        }
    }

    return dummy.next;
}

private ListNode reverse(ListNode head, ListNode tail) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode prev = null, temp = null;
    while ((head != null) && (head != tail)) {
        temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }

    return prev;
}