hard Reverse Nodes in k-Group

Problem Statement

Given the head of a linked list, reverse each k node of the list at a time and return the modified list.

Here, 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, the remaining nodes at the end should stay as they are.

Note: You can only change the nodes themselves, not the values inside them.

Examples

1. Example 1:

   • Input: head = [1, 2, 3, 4, 5, 6], k = 3
   • Expected Output: [3, 2, 1, 6, 5, 4]
   • Justification: The list is reversed in groups of three. First group [1, 2, 3] becomes [3, 2, 1] and the second group [4, 5, 6] becomes [6, 5, 4].

2. Example 2:

   • Input: head = [1, 2, 3, 4, 5], k = 2
   • Expected Output: [2, 1, 4, 3, 5]
   • Justification: The list is reversed in groups of two. First group [1, 2] becomes [2, 1] and the second group [3, 4] becomes [4, 3]. The last node [5] remains unchanged.

3. Example 3:

   • Input: head = [1, 2, 3, 4, 5, 6, 7], k = 4
   • Expected Output: [4, 3, 2, 1, 5, 6, 7]
   • Justification: The list is reversed in groups of four. First group [1, 2, 3, 4] becomes [4, 3, 2, 1]. The remaining nodes [5, 6, 7] are left as they are because their count is less than k.

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Solution

To solve this problem, we will traverse the linked list and reverse every k nodes. We need to handle the reversal in-place, ensuring we only modify the pointers of the nodes. We must also manage the situation where the number of nodes remaining at the end of the list is less than k, in which case those nodes should not be reversed. This approach is effective because it ensures that the nodes are only traversed once, giving an time complexity, where n is the number of nodes in the list.

We will use a loop to process each group of k nodes. For each group, we will reverse the nodes by adjusting the pointers. After reversing each group, we will reconnect it to the previous part of the list. This method ensures that the nodes are reversed in place and the list remains properly connected.

Step-by-step Algorithm

1. Initialize a dummy node: Create a dummy node and set its next pointer to the head of the linked list. This dummy node will help manage the list manipulation easily.

2. Initialize pointers: Set two pointers, groupPrev and groupNext, to the dummy node. These pointers will help in identifying the beginning and the end of the group to be reversed.

3. Iterate through the linked list: Use a loop to iterate through the linked list.

   • Move the groupNext pointer k nodes ahead: Increment a counter to count nodes and move the groupNext pointer until it reaches k nodes ahead. If there are less than k nodes remaining, break out of the loop.

4. Reverse the k nodes:

   • Set the initial pointers for reversal: Set a prev pointer to the node next to groupPrev and a curr pointer to the node next to prev.
   • Perform the reversal: Use a loop to reverse the k nodes. For each node in the group, adjust the pointers to reverse the links. Move the curr pointer to the next node after each reversal.

5. Move the groupPrev pointer: After reversing the k nodes, move the groupPrev pointer k nodes ahead to the end of the reversed group.

6. Return the new head: After the loop completes, return the next node of the dummy node as the new head of the modified list.

Algorithm Walkthrough

Let's walkthrough the algorithm for head = [1, 2, 3, 4, 5, 6], k = 3

1. Initialization:

   • Create a dummy node: dummy = ListNode(0), dummy.next = head
   • Initialize pointers: groupPrev = dummy, groupNext = dummy

2. First Iteration:

   • Move groupNext pointer k nodes ahead:
     • Move to groupNext = groupNext.next (1)
     • Move to groupNext = groupNext.next (2)
     • Move to groupNext = groupNext.next (3)
   • Check if there are k nodes:
     • groupNext is not null, so continue.

3. Reverse the first k nodes:

   • Set initial pointers: prev = groupPrev.next (1), curr = prev.next (2)
   • Reversal process:
     • Step 1:
       • prev.next = curr.next (1 -> 3)
       • curr.next = groupPrev.next (2 -> 1)
       • groupPrev.next = curr (dummy -> 2)
       • curr = prev.next (3)
       • List state: dummy -> 2 -> 1 -> 3 -> 4 -> 5 -> 6
     • Step 2:
       • prev.next = curr.next (1 -> 4)
       • curr.next = groupPrev.next (3 -> 2)
       • groupPrev.next = curr (dummy -> 3)
       • curr = prev.next (4)
       • List state: dummy -> 3 -> 2 -> 1 -> 4 -> 5 -> 6
   • Move groupPrev pointer k nodes ahead: groupPrev = prev (1)

4. Second Iteration:

   • Move groupNext pointer k nodes ahead:
     • Move to groupNext = groupNext.next (4)
     • Move to groupNext = groupNext.next (5)
     • Move to groupNext = groupNext.next (6)
   • Check if there are k nodes:
     • groupNext is not null, so continue.

5. Reverse the second k nodes:

   • Set initial pointers: prev = groupPrev.next (4), curr = prev.next (5)
   • Reversal process:
     • Step 1:
       • prev.next = curr.next (4 -> 6)
       • curr.next = groupPrev.next (5 -> 4)
       • groupPrev.next = curr (1 -> 5)
       • curr = prev.next (6)
       • List state: dummy -> 3 -> 2 -> 1 -> 5 -> 4 -> 6
     • Step 2:
       • prev.next = curr.next (4 -> null)
       • curr.next = groupPrev.next (6 -> 5)
       • groupPrev.next = curr (1 -> 6)
       • curr = prev.next (null)
       • List state: dummy -> 3 -> 2 -> 1 -> 6 -> 5 -> 4
   • Move groupPrev pointer k nodes ahead: groupPrev = prev (4)

6. End of list:

   • The loop ends as there are no more nodes to process.

7. Return the new head:

   • Return dummy.next which points to the new head of the reversed list: 3 -> 2 -> 1 -> 6 -> 5 -> 4

Code

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

public class Solution {

  public ListNode reverseKGroup(ListNode head, int k) {
    // Dummy node initialization
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // Initialize pointers
    ListNode groupPrev = dummy;
    ListNode groupNext = dummy;

    // Loop through the list
    while (true) {
      int count = 0;
      // Move groupNext pointer k nodes ahead
      while (count < k && groupNext != null) {
        groupNext = groupNext.next;
        count++;
      }
      // If there are less than k nodes remaining, break
      if (groupNext == null) break;

      // Initialize pointers for reversing
      ListNode prev = groupPrev.next;
      ListNode curr = prev.next;

      // Reverse k nodes
      for (int i = 1; i < k; i++) {
        prev.next = curr.next;
        curr.next = groupPrev.next;
        groupPrev.next = curr;
        curr = prev.next;
      }

      // Move the groupPrev pointer k nodes ahead
      groupPrev = prev;
      groupNext = prev;
    }
    return dummy.next;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    ListNode head1 = new ListNode(1);
    head1.next = new ListNode(2);
    head1.next.next = new ListNode(3);
    head1.next.next.next = new ListNode(4);
    head1.next.next.next.next = new ListNode(5);
    head1.next.next.next.next.next = new ListNode(6);
    ListNode result1 = sol.reverseKGroup(head1, 3);
    printList(result1);

    // Example 2
    ListNode head2 = new ListNode(1);
    head2.next = new ListNode(2);
    head2.next.next = new ListNode(3);
    head2.next.next.next = new ListNode(4);
    head2.next.next.next.next = new ListNode(5);
    ListNode result2 = sol.reverseKGroup(head2, 2);
    printList(result2);
  }

  public static void printList(ListNode head) {
    while (head != null) {
      System.out.print(head.val + " ");
      head = head.next;
    }
    System.out.println();
  }
}

Complexity Analysis

• Time Complexity: The algorithm traverses each node in the list a constant number of times. Therefore, the time complexity is , where (n) is the number of nodes in the list.
• Space Complexity: The algorithm uses a constant amount of extra space regardless of the input size. Therefore, the space complexity is .