Leetcode 25

题目要求

每K个节点一组进行链表翻转

核心算法和原理

• 先计算总结点个数n，每次翻转减k

• 维护cur, pre和nxt，pre可初始化为nullptr 常规操作进行反转即可

• 维护一个preEnd节点，表示上一次翻转后的末尾节点 在常规翻转结束后，维护preEnd->next以及 本次翻转的末尾节点的next

• 整个过程的循环不变量：pre在循环结束后一定是上一次翻转后的起始节点；cur一定是下一次翻转前的起始节点

• dummy node的引入：第一次翻转时不存在preEnd，构造一个方便边界条件的判断；同时dummy.next可以直接表示翻转后的头部节点

代码

/**
 * 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 (k == 1) {
            return head;
        }
        int n = 0;
        for (ListNode* node = head; node; node = node->next) {
            n++;
        }

        ListNode dummy(0, head);
        ListNode* preEnd = &dummy;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nxt;

        for (; n >= k; n -= k) {
            for (int i = 0; i < k; i++) {
                nxt = cur -> next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }
            
            ListNode* tmp = preEnd->next;
            preEnd->next->next = cur;
            preEnd->next = pre;
            preEnd = tmp;
        }
        
        return dummy.next;
    }
};