<Data Structures/Algorithms> leetcode hot100 - 25. Reverse Nodes in k-Group

[LeetCode Hot 100] 25. Reverse Nodes in k-Group

Problem Link

This is a tricky problem and requires some careful thinking.

We have already solved LeetCode 206: Reverse Linked List, where the idea is to keep a previous node and, in each step, point the next of the current node to the previous node. In this problem, the reversal within each group of k nodes can be handled similarly.

The main difficulty is how to connect the locally reversed sublist back to the original list. Here’s a rough illustration (assuming k=2):

A tricky part here is setting prev. To determine the last node of a group of k nodes, we use a fast and slow pointer. The fast pointer is k nodes ahead of the slow pointer, and both move k nodes each iteration. The slow pointer points to the node before the current k nodes (its next points to the first node of the group), while the fast pointer points to the last node of the current group. When reversing the first group, prev is set to nullptr because the original first node becomes the last node, which should point to null. However, for each group, after the first node becomes the last node, it needs to point to the head of the next group, so prev should initially point to fast->next before starting the reversal of the group.

After reversing a group, the tail of the group is already connected to the next group. But note that the head of each group changes after reversal. After traversal, the previous group’s tail should point to the new head of the reversed group. The new head is the position of prev after reversal, and the previous tail is slow. So we need slow->next = prev.

It’s a bit tricky, so looking at the diagram helps.

Complete code is as follows:

/**
 * 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) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = fast;

        while(fast){
            for(int i = 0; i < k; i++){
                if(!fast->next) return dummy.next;
                fast = fast->next;
            }
            ListNode* prev = fast->next;
            ListNode* cur = slow->next;
            while(prev != fast){
                ListNode* tmp = cur->next;
                cur->next = prev;
                prev = cur;
                cout<<cur->val<<endl;
                cur = tmp;
            }
            
            ListNode* newEnd = slow->next;
            newEnd->next = cur;
            slow->next = fast;
            slow = fast = newEnd;
            
        }
        return dummy.next;
    }
};

中文原文

[LeetCode hot 100] 25. k个一组翻转链表

题目链接

好折磨的题，要想明白还真是得费一些脑筋。

我们已经做过LeetCode 206 反转链表，直到反转链表的思路是保留一个前驱节点，然后每次让后继结点的next指向前驱节点。这个题中对于每一组中的反转自然也可以这样做。

不过难点就在于局部反转后怎样和原链表接起来。思路我大致画了个图（假设k=2）：

这里有个很tricky的点，就是这个prev的设置。由于我们需要确定一组k个节点中的最后一个，所以需要使用快慢指针，快指针比慢指针领先k，并且二者每轮同时后移k个。慢指针是当前k个的前一个，也就是next指向当前k个中第一个的节点，而快指针就是当前k个的最后一个。在反转整个链表时，我们首先令prev=nullptr，这是因为原先的第一个节点会变成最后一个，而最后一个节点的next指向的就是null。但是这里不同，我们每一组的第一个节点变成最后一个节点后，还需要指向下一组的头，所以prev在每组开始反转的时候都应该先指向下一组的头，那么这个下一组的头就是fast->next。

每组反转之后，这一组的尾就已经接在下一组的头上了，但是注意，每一组的头都会变的，所以在遍历之后应该让上一组的尾重新指向这个新的头。新的头就是反转结束后prev的位置，而上一组的尾就是slow，所以需要slow->next = prev;

挺绕的，还是看图好懂一点吧~

完整代码如下

/**
 * 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) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = fast;

        while(fast){
            for(int i = 0; i < k; i++){
                if(!fast->next) return dummy.next;
                fast = fast->next;
            }
            ListNode* prev = fast->next;
            ListNode* cur = slow->next;
            while(prev != fast){
                ListNode* tmp = cur->next;
                cur->next = prev;
                prev = cur;
                cout<<cur->val<<endl;
                cur = tmp;
            }
            
            ListNode* newEnd = slow->next;
            newEnd->next = cur;
            slow->next = fast;
            slow = fast = newEnd;
            
        }
        return dummy.next;
    }
};