【力扣hot100】25 K个一组反转链表（c++）解析

这是一题比较简单的hard
思路和模拟方法相同，首先判断链表是否有K个数，不足则直接返回head。否则对前K个数进行反转，然后进行递归处理。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *p = head;
        for(int i = 0; i < k; i++) { //判断是否链表的长度小于k
            if(!p) return head;
            p = p->next;
        }
		//用草稿纸画画就出来了，抓住q指向pre这个条件
		//在这个循环中，程序执行实际的反转操作。它将当前节点 q 的 next 指针指向前一个节点 pre，然后更新 pre 和 q 指针，继续移动到下一个节点。这样，链表中的一组长度为k的节点被反转。
        ListNode *q = head;
        ListNode *pre = nullptr;
        while(q != p) {
            ListNode *tmp = q->next;
            q->next = pre;
            pre = q;
            q = tmp;
        }
		//最后，函数递归地调用自身，对剩余的链表部分进行反转，并将反转后的链表的头部连接到当前已反转的部分。然后，函数返回已反转的部分的头部指针 pre
        head->next = reverseKGroup(p, k);
        //将当前已经反转过的部分链表的末尾节点的 next 指针连接到剩余部分链表（即下一组待反转的链表）的反转结果
        return pre;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25