25. K 个一组翻转链表

zhou2023-10-222023-10-22

25. K 个一组翻转链表

25. K 个一组翻转链表

题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

首先是k的不确定导致我们需要得知有多少个总的节点，才能实现题目的要求，所以先统计节点个数。

剩下的实现有两个关键点：第一个是如何翻转链表，第二个是哨兵节点

如何翻转链表

翻转的第一步得是翻转1，2，3，4之间的顺序

然后把4放到前面，把1放到后面，让1指向5

接下来我们详细进行实现

如果我们要改变一个节点的顺序，我们得把当前节点的next变成pre，所以我们一共要记录三个节点。

如果我们需要改变2的顺序（在此之前已经改变了1的顺序了）然后我们将cur->next = pre

接着把指针们都往后移

也就是

pre = cur

cur = nxt

nxt = nxt.next

后面往复便可以了，值得一提的是k个节点之后，我们需要将前后拼接起来

具体的操作：

在后半段，我们刚处理完，情况是这样的

最后我们要把1节点连接到8节点上，把5节点的next记为nullptr。我们先把1节点记为P0

那么。我们需要做这样的操作：

P0->next->next = null

P0->next = pre

为了方便下一段k操作，我们还需要更新P0

P0 = P0->next

因为数据在更新，所以我们得调整一下顺序和形式，（注意每次P0->next所代指的节点到底是哪个）总的代码是：

auto nxt = P0->next

P0->next->next = null

P0->next = pre

P0 = nxt

哨兵节点

在上面展示的过程中，我们是以5-8为举例的，但如果我们要处理的数据是1-4的话，我们会没有P0可用，所以我们需要一个哨兵节点来当P0，具体的实现是：

ListNode *dummy = new ListNode(0, head), *p0 = dummy;

使用一个新链表，添加一个节点0，指向head

处理完第一段k就让0节点的next指向4，更新P0，让P0指针指向下一段k的P0的位置就可以了

代码

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        int n = 0;
        for (ListNode *cur = head; cur; cur = cur->next)
            ++n; // 统计节点个数

        ListNode *dummy = new ListNode(0, head), *p0 = dummy;
        ListNode *pre = nullptr, *cur = head;
        for (; n >= k; n -= k) {
            for (int i = 0; i < k; ++i) { 
                ListNode *nxt = cur->next;
                cur->next = pre; 
                pre = cur;
                cur = nxt;
            }
            ListNode *nxt = p0->next;
            p0->next->next = cur;
            p0->next = pre;
            p0 = nxt;
        }
        return dummy->next;
    }
};