25. Reverse Nodes in k-Group - Detailed Explanation

Problem Statement

Description:
Given a linked list, 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, then the last remaining nodes should be left in their original order.
• You may not alter the values in the nodes—only the nodes themselves may be changed.

Example 1:

• Input: head = [1, 2, 3, 4, 5], k = 2
• Output: [2, 1, 4, 3, 5]
• Explanation:
  • The first group [1, 2] is reversed to [2, 1].
  • The second group [3, 4] is reversed to [4, 3].
  • The last node [5] remains as it is since the group size is less than 2.

Example 2:

• Input: head = [1, 2, 3, 4, 5], k = 3
• Output: [3, 2, 1, 4, 5]
• Explanation:
  • The first group [1, 2, 3] is reversed to [3, 2, 1].
  • The remaining group [4, 5] is left as is because its size is less than 3.

Constraints:

• The number of nodes in the list is in the range [1, 5000].
• 1 ≤ k ≤ the length of the list.
• The values of the nodes are not important for the reversal; only the nodes and their connections are changed.

Hints

• Hint 1:
  Think about how you would reverse a simple linked list. How can you adapt that to only reverse k nodes at a time?

• Hint 2:
  Use a dummy node to simplify edge cases (especially when the head of the list changes). You may need pointers to mark the beginning and end of the current k-group.

• Hint 3:
  Before reversing a group, ensure that there are at least k nodes remaining. If not, simply attach the remaining part without reversing.

Approach 1: Iterative Solution with Dummy Node

Idea

1. Count k Nodes:
   For each group, first check whether there are k nodes available.
2. Reverse k Nodes:
   Reverse the group of k nodes using the typical linked list reversal technique.
3. Link Groups:
   After reversing, connect the reversed group to the previous part and set up for the next group.
4. Continue Until End:
   Stop when there are fewer than k nodes left.

Detailed Steps

1. Setup a Dummy Node:
   Create a dummy node that points to the head of the list. This simplifies handling edge cases where the head changes after reversal.

2. Initialize Pointers:

   • prevGroupEnd initially points to the dummy node.
   • groupStart points to the first node of the current group.
   • Traverse to find groupEnd, which is the kth node of the current group.

3. Reverse the Group:
   Reverse the nodes between groupStart and groupEnd.
   Use three pointers (prev, curr, and next) to reverse the links.

4. Reconnect the List:
   After reversing, connect the previous group’s end (prevGroupEnd) to the new start of the reversed group, and connect the old start (which becomes the end of the reversed group) to the next node after the group.

5. Move to Next Group:
   Set prevGroupEnd to the end of the reversed group and repeat for the next group.

Visual Walkthrough

For the list: 1 → 2 → 3 → 4 → 5 and k = 2:

• First Group:

  • Group: 1 → 2
  • Reverse to: 2 → 1
  • Connect dummy → 2 → 1

• Second Group:

  • Next group: 3 → 4
  • Reverse to: 4 → 3
  • Connect 1 → 4 → 3

• Remaining:

  • Node 5 remains unchanged.
  • Final list: dummy → 2 → 1 → 4 → 3 → 5

Code Implementation

Python Code