Reverse Nodes in k-Group - Java Solution

1. Introduction

This blog post discusses the "Reverse Nodes in k-Group" problem, a notable challenge in linked list manipulation. The task involves reversing every k nodes in a linked list, which tests the understanding of linked list traversal and modification. This problem is a step-up from simple linked list reversal and requires more intricate pointer manipulation.

Problem

Given the head of a linked list, the goal is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes should stay as they are. The values in the nodes should not be altered, only the nodes themselves may be changed.

2. Solution Steps

1. Define a function reverseKGroup which takes the head of the list and an integer k.

2. Create a dummy node to handle edge cases smoothly.

3. Use pointers prev, current, and next to track and reverse k nodes at a time.

4. Check if there are k nodes to reverse; if not, leave the remaining nodes as they are.

5. Reverse k nodes by adjusting their pointers.

6. Link the reversed group back to the rest of the list.

7. Continue this process until all groups of k nodes are reversed.

8. Return the head of the modified list.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseNodesInKGroup {
    public static void main(String[] args) {
        // Example use case
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode result = reverseKGroup(head, 2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    // Function to reverse nodes in k-group
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy, prev = dummy, next = dummy;
        int count = 0;

        // Count the number of nodes in the list
        while (current.next != null) {
            current = current.next;
            count++;
        }

        while (count >= k) {
            current = prev.next;
            next = current.next;
            for (int i = 1; i < k; i++) {
                current.next = next.next;
                next.next = prev.next;
                prev.next = next;
                next = current.next;
            }
            prev = current;
            count -= k;
        }

        return dummy.next;
    }
}

Output:

2 1 4 3 5

Explanation:

1. reverseKGroup: This function handles the process of reversing every k nodes in the linked list.

2. A dummy node is used to simplify handling of the head of the list and edge cases.

3. The function first counts the total number of nodes in the list.

4. If there are at least k nodes left, it reverses the next k nodes. The reversal is done by adjusting the pointers within the group and linking the group correctly with the rest of the list.

5. The process repeats until there are fewer than k nodes left, which are left as-is.

6. The function returns the new head of the list, which is the next node of the dummy node.

7. This method efficiently reverses nodes in groups of k using pointer manipulation, adhering to the constraints of not altering node values and handling lists with lengths not divisible by k.