如何将链表每k个元素反转，形成长尾？

本文共计1120个文字，预计阅读时间需要5分钟。

题目：给你链表的头节点 +head+，每 +k+ 个节点进行一组循环，请返回修改后的链表。

+k+ 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 +k+ 的整数倍，那么请将最后多余的节点保留。

例如，给定链表：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10，+k+=3，则修改后的链表为：1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> 4 -> 5 -> 6。

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

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

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

示例 1：

示例 2：

解题思路

对于这道题目我们可以先写一个1函数这个1函数的两个参数分别是链表的两个节点，而这个1函数的功能就是翻转这两个节点之间所有的节点，然后返回翻转链表后新的头。这里我们假设要反转的那两个节点的名字是a，b那么经过一次反转之后a就变成了尾节点（这里的b不是头节点，至于为什么我们下面的代码阶段我会给出解释），并且返回这一段新的头，那么接下来我们的目的就是让原链表所有的节点都要经过一次1函数，那么假设我们已经以k为一组完成了所有函数的翻转，下一步就是如何将这些连接起来。接下来我们就要使用递归的方式来解决了我们这里先看代码之后我们结合代码以及图来分析

这个代码是用于翻转两个节点之间所有的节点的

struct ListNode* reserve(struct ListNode* a, struct ListNode* b) { struct ListNode* pre = NULL; struct ListNode* start = a, * end = a; while (start != b) { end = end->next; start->next = pre; pre = start; start = end; } return pre;//最后返回反转链表之后的新头节点 }

下面就是主函数：

struct ListNode* reverseKGroup(struct ListNode* head, int k) { if (head == NULL) return NULL; //解题思路使用递归，首先我们完成一个函数这个函数的目的是反转两个节点之间的链表，并且返回头节点 struct ListNode* a = head, * b = head; for (int i = 0; i < k; i++) { if (b == NULL) return head; b = b->next; } struct ListNode* newhead = reserve(a, b);//经过反转之后现在的a指向的就是反转链表的最后一个节点 a->next = reverseKGroup(b, k);//然后继续从b开始往后继续倒转k个节点 return newhead; }

那么这里我们就举个例子并结合例子以图来解释，我们就是示例1为例子

我们走读代码很显然当我们走读到第12行的时候，链表里面的逻辑图就变成了下面这样

第一次翻转后：

然后这里返回的节点是2，也就是此时的newhead指针储存的就是节点2里面的地址，然后我们看下一步是改变了a的next，通过翻转函数可以看到我们并没有改变a的指向所以这里的a指向的仍然是1，所以改变1的next让其能够连接翻转后的节点，可以看到下一步我们就递归调用自己了，而这里的头节点变成了b，通过图我们也可以看到b刚好就是下一组的新头，我们在画一次图这一次我们设定a'和b'作为新指针便于观察理解。

第一次递归：

下面我们将调用函数内部的a‘和b’之间的节点反转

逻辑图：

之后返回的是4节点然后下一步a'的next等于我们再一次递归，但是这第二次递归当执行到（这里的b是第二次递归里面创建的b赋值为b‘）b==NULL时就直接返回了b'，返回的值就让第一次递归的a'的next成功赋值变成了

然后在第一次递归的最后返回了4的值赋给了最外层a的next让其变成了

最后返回2的节点，完成题目。