力扣题目k个一组翻转链表

来源：互联网收集：自由互联发布时间：2023-09-03

题目：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余

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

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

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

示例 1：

力扣题目k个一组翻转链表_赋值

示例 2：

力扣题目k个一组翻转链表_链表_02

解题思路

对于这道题目我们可以先写一个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行的时候，链表里面的逻辑图就变成了下面这样

力扣题目k个一组翻转链表_数据结构_03

第一次翻转后：

力扣题目k个一组翻转链表_递归_04

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

第一次递归：

力扣题目k个一组翻转链表_数据结构_05