25. Reverse Nodes in k-Group (Hard)

https://leetcode.com/problems/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.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Solutions

class Solution {

    // The key idea is to sort out the length of the given list first. Then reverse the legitimate groups
    // only, in other words, you don't have to care about the nodes that can't form a group of size k.
    // Finally, handle each group separately. It is advised to reverse elements in the group as the way
    // insertion sort does. The trick is to prepend the element at the head in each iteration.

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        int len = 0;

        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }

        // k = 3, dummy->n1->n2->n3->n4
        head = dummy;

        // only on the event that the size of group is k, then it can be reversed
        for (int i = 0; i < len / k * k; i++) {
            if (i % k == 0) {
                reverseGroupElements(head, k);
            }

            head = head.next;
        }

        return dummy.next;
    }

    private ListNode reverseGroupElements(ListNode head, int k) {
        if (head.next == null) {
            return null;
        }

        // head->p1->p2->p3->p4, k = 3
        // head->p2->p1->p3->p4
        // head->p3->p2->p1->p4

        ListNode p1 = head.next;
        ListNode p2 = p1.next;

        // If it is allowed to swap values in node, it will be much easier.
        for (int i = 1; i < k; i++) {
            if (p2 == null) {
                break;
            }

            p1.next = p2.next;

            // p2.next should be head.next, rather than p1
            p2.next = head.next;

            head.next = p2;

            p2 = p1.next;
        }

        return head.next;
    }
}

Incorrect Solutions

References