题解 | #链表中的节点每k个一组翻转# 【模拟】详细注释双超100

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

解题思路

本题是一道模拟题，按题给条件模拟即可，难的是本题细节很多。如果是普通的翻转链表，那么很简单。但是按k个一组翻转的话，你不光要正确地翻转本组节点，还要能让上一组的尾结点链接到本组的头部，并且将本组节点的尾部链接到下一组的头部。这里使用两个指针tailOfLastVisited，headOfFirstUnVisited分别指向已遍历到的节点的尾部和未开始遍历的节点的头部，那么显然，对于每组节点，我们需要将tailOfLastVisited指向的节点的next指针指向下一组节点中headOfFirstUnVisited指向的节点。为了方便返回答案和边界处理，我们新建一个假头节点ans。初始时，ans的next指针指向head，tailOfLastVisited，headOfFirstUnVisited分别指向ans和head，之后开始向右移动headOfFirstUnVisited指针，使用一个计数器count记录headOfFirstUnVisited移动的次数，当headOfFirstUnVisited移动k-1次时，使用临时指针temp指向tailOfLastVisited指针指向的节点的下一节点，将tailOfLastVisited指针指向节点的next指针指向headOfFirstUnVisited指针指向的节点，第一次执行该操作时，也即将ans节点的后继结点设置为第一组带翻转节点的尾节点。不难理解，返回答案的头节点，必然是第一组待翻转节点的最后一个节点，即headOfFirstUnVisited指针后移k-1次后指向的节点（初始时指向head），之后更新tailOfLastVisited指针为temp指针指向的节点。当headOfFirstUnVisited指针移动k次时，开始翻转headOfFirstUnVisited之前的k个节点。若移动不足k次，headOfFirstUnVisited就指向了null，则不做处理。组内翻转及其他细节详见注释。 alt

代码

/**
 * 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) {
        if(head==nullptr || head->next==nullptr || k==1) return head;//如果链表为空或者只有一个节点或者k为1则直接返回head
        ListNode* ans = new ListNode(0);//新建假头节点方便返回答案和边界处理
        ans->next = head;//ans指向head
        ListNode* tailOfLastVisited = ans;//已遍历节点组的尾节点，也即将要处理的节点组的尾结点，处理完该节点会成为该组节点的头节点
        ListNode* headOfFirstUnVisited = head;//未遍历节点的头节点
        int count = 0;//计数器
        while(headOfFirstUnVisited != nullptr){//持续右移直至为空
            headOfFirstUnVisited = headOfFirstUnVisited->next;
            count++;
            if(count==k-1 && headOfFirstUnVisited != nullptr){//如果移动次数为k-1
                //则表明该节点在处理完后会成为该组节点的头节点，所以将上一组节点的尾结点的后继结点设为该节点
                ListNode* temp = tailOfLastVisited -> next;
                tailOfLastVisited -> next = headOfFirstUnVisited;
                tailOfLastVisited = temp;//同时更新tailOfLastVisited节点
            }
            if(count==k && headOfFirstUnVisited != nullptr){//如果移动次数为k次，则对前面一组k个节点进行翻转处理
                ListNode* low = headOfFirstUnVisited;//已翻转节点的尾节点
                ListNode* mid = tailOfLastVisited;//待翻转节点
                ListNode* high = mid->next;//下一待翻转节点
                while(mid != headOfFirstUnVisited){//处理至下一节点为headOfFirstUnVisited
                    mid -> next = low;//翻转当前节点
                    low = mid;//更新low，mid，high
                    mid = high;
                    high = high->next;
                }
                count = 0;//重置计数器
            }
            //当链表长刚好为k的倍数时，上一代码块的处理会有问题，这里偷了个懒直接加了一段代码，就懒得优化合并了，大同小异
            if(count==k && headOfFirstUnVisited == nullptr){
                ListNode* low = nullptr;//尾结点的下一节点置为空，其他没太大区别
                ListNode* mid = tailOfLastVisited;
                ListNode* high = mid->next;
                while(high != nullptr){
                    mid -> next = low;
                    low = mid;
                    mid = high;
                    high = high->next;
                }
                mid -> next = low;
            }
        }
        return ans->next;//返回答案
    }
};