Leetcode Study Day 29

Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:


Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:


Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
 

Constraints:

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

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
	ListNode* reverseKGroup(ListNode* head, int k) {
        // copy of the head
        ListNode* cursor = head;
        for(int i = 0; i < k; i++){
            // if the length is not enough for reverse
            if(cursor == nullptr) return head;
            cursor = cursor->next;
        }
        // copy of the head
        ListNode* curr = head;
        ListNode* prev = nullptr;
        ListNode* nxt = nullptr;
        // reverse the list
        for(int i = 0; i < k; i++){
            nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        head->next = reverseKGroup(curr, k);
        return prev;
    }
};

In the reverse function, let’s used an example to explain the logic:

Consider a portion of the linked list:

A→B→C→D→E→F→…

Let’s assume k=3, so we want to reverse the first three nodes (A, B, C). After reversing:

C→B→A→D→E→F→…

Now, let’s use the code to understand how this happens:

1. Initial setup:
   prev → null

curr → A

nxt → null

2. First iteration (i = 0):
   nxt → B

curr
(
A’s next
)
→
null

prev
→
A

curr
→
B

After this iteration:

A←B→C→D→E→F→…

3. Second iteration (i = 1):
   nxt
   →
   C
   curr
   (
   B’s next
   )
   →
   A

prev
→
B

curr
→
C

After this iteration:

A←B←C→D→E→F→…

4. Third iteration (i = 2):
   nxt
   →
   D

curr
(
C’s next
)
→
B

prev
→
C

curr
→
D

After this iteration:

A←B←C→D→E→F→…

After these three iterations, the reversal of the first three nodes is complete. The key thing to note is how the pointers (prev, curr, and nxt) are used to reverse the pointers of the nodes in the linked list.