Leetcode.com problem 25: "Reverse Nodes in k-Group"

James S. Plank

• Problem Statement.
• Success Rate (as of August, 2022): 52.5%
• Rated a "hard" problem.

Testing

int main()
{
  ListNode *r, *l, *nn;
  int n, k;
  Solution s;

  cin >> k;                   // Read k first, and then read the nodes of the list.

  r = NULL;                   // I'm keeping track of the last node, so I can create
  while (cin >> n) {          // this list in order.  I always add the new node as
    nn = new ListNode(n);     // the next field of the last node I created.
    if (r == NULL) {
      r = nn;
      l = nn;
    } else {
      l->next = nn;
      l = nn;
    }
  }

  r = s.reverseKGroup(r, k);         // Call the method.

  for (l = r; l != NULL; l = l->next) {   // And print out the resulting list.
    printf("%d ", l->val);
  }
  printf("\n");
  return 0;
}

UNIX> echo 3    1 2 3 4 5 6 7 8 | ./a.out
3 2 1 6 5 4 7 8 
UNIX> echo 2    1 2 3 4 5 6 7 8 | ./a.out            # This one will seg fault if you're not careful,
2 1 4 3 6 5 8 7                                      # so make sure you test it.
UNIX> 

Organizing your solution

Now, I recursively call reverseKGroup() on after_k. When I'm done, I store the return value into a new pointer called rest. In this example, it will reverse the 4-5-6, and return a pointer to 6. You'll note, that after_k is still pointing to the 4. Here's the picture:

Now, I'm ready to reverse the three nodes starting at head. What I do is use three more pointers: prev, l and next. I set them to head, head->next and head->next->next respectively. Since k is at least two, these will all exist (although next may be NULL if k is two and the list has only two elements):

I switch l->next so it points to prev, and then I move prev, l and next to be the next nodes:

I repeat the previous steps (they're in a loop):

Now, you'll note that l equals after_k. This means you can exit your loop. Your last two steps are setting head to point to rest, and then you'll return prev:

Before you go coding and submitting, you should work through yourself what happens when after_k points to NULL. You'll have to check that case when you're setting next in the loop above, to avoid a seg-fault (I know from experience...).