25. Reverse Nodes in k-Group (Hard) Facebook Microsoft 低频

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

kis 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 ofkthen 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

Fork= 2, you should return:2->1->4->3->5

Fork= 3, you should return:3->2->1->4->5

Solution 1: Iterative O(n); O(1)

    /**
     * Iterative O(n); O(1)
     * Divide linked list into two parts:
     * The first K nodes as a group, L1, might not exist. The rest of the linked list, L2.
     * So first we move a pointer to the head of L2.
     * If we reach the end before K step, no more reverse, break and return.
     * If we find the head of L2, restHead, use it as a stop point for reverse.
     * Then we reverse the current group.
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy; // Current group dummy. Or the tail of previous group.
        ListNode cur = head; // Current group head.

        while (cur != null) {
            ListNode rest = cur;
            int group = k;
            while (rest != null && group > 0) { // Find nextHead.
                group--;
                rest = rest.next;
            }
            if (group > 0) { // Reach list end.
                break;
            }
            // Similar to reverse linked list.
            while (cur.next != rest) { // Ends at the head of remaining list.
                ListNode temp = cur.next.next;
                cur.next.next = pre.next;
                pre.next = cur.next;
                cur.next = temp;
            }
            pre = cur; // Move current dummy to the end of current group.
            cur = cur.next; // Move current head to the next group.
        }
        return dummy.next;
    }