25. K 个一组翻转链表

🔴   🔖  递归 链表  🔗 力扣 LeetCode

题目

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2

Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3

Output: [3,2,1,4,5]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

题目大意

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

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

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

解题思路

这一题是 第 24 题 的加强版，第 24 题是两两相邻的元素，翻转链表。而本题要求的是 k 个相邻的元素，翻转链表，第 24 题相当于是 k = 2 的特殊情况。

思路一：迭代法

1. 使用 dummy 作为虚拟头节点，方便处理链表的连接和首节点的反转；
2. 首先遍历链表，获取链表长度 length，用于判断是否有足够的 k 个节点进行反转；
3. 每次找到 k 个节点进行反转，通过循环来交换节点的位置，并保持链表正确的连接顺序；
4. 反转完成后，将指针 prev 移动到下一组的前一个节点，继续遍历下一组 k 个节点，直到剩余节点不足 k；

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

---

思路二：递归法

1. 判断是否足够 k 个节点：在每次递归之前，遍历前 k 个节点，判断是否有足够的 k 个节点。如果不足 k 个，则直接返回当前链表，不进行反转。
2. 反转前 k 个节点：通过循环逐个反转 k 个节点。使用 prev 来记录已经反转的部分，curr 用来遍历当前节点，next 记录下一个节点的位置。
3. 递归处理剩余部分：在反转 k 个节点后，递归处理剩余的链表部分，并将递归结果连接到反转后的链表。
4. 返回结果：每次递归都返回反转后的链表头节点。

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n/k)，递归方式更加直观，反转过程简洁，但递归栈的深度为 O(n/k)。

代码

迭代法

var reverseKGroup = function (head, k) {
	// 创建虚拟头节点，方便处理链表连接
	let dummy = new ListNode(0);
	dummy.next = head;
	let prev = dummy;

	// 统计链表长度
	let length = 0;
	let temp = head;
	while (temp) {
		length++;
		temp = temp.next;
	}

	// 逐步反转每组k个节点
	while (length >= k) {
		let curr = prev.next;
		let next = curr.next;
		for (let i = 1; i < k; i++) {
			curr.next = next.next;
			next.next = prev.next;
			prev.next = next;
			next = curr.next;
		}
		// 移动指针到下一组
		prev = curr;
		length -= k;
	}

	return dummy.next;
};

递归法

var reverseKGroup = function (head, k) {
	// 判断剩余节点是否足够k个，不够则返回原链表
	let count = 0;
	let node = head;
	while (count < k && node) {
		node = node.next;
		count++;
	}
	if (count < k) {
		return head;
	}

	// 反转前k个节点
	let prev = null;
	let curr = head;
	let next = null;
	for (let i = 0; i < k; i++) {
		next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
	}

	// 递归处理剩下的链表，并连接到反转后的链表
	head.next = reverseKGroup(curr, k);

	// 返回反转后的头节点
	return prev;
};

递归法 2

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
	let node = head;
	// 将 node 指向第 k + 1 个节点
	for (let i = 0; i < k; i++) {
		// 若不足 k 个节点，直接返回 head
		if (!node) {
			return head;
		}
		node = node.next;
	}
	// 翻转 1 ~ k 之间的节点
	let newHead = reverse(head, node);
	// 递归，继续反转后面的节点
	head.next = reverseKGroup(node, k);
	return newHead;
};

// 反转的 first ~ last - 1 之间的节点
/**
 * @param {ListNode} first
 * @param {ListNode} last
 * @return {ListNode}
 */
var reverse = function (first, last) {
	let res = new ListNode(0, first);
	while (first.next != last) {
		let temp = first.next;
		first.next = temp.next;
		temp.next = res.next;
		res.next = temp;
	}
	return res.next;
};

相关题目

题号	标题	题解	标签	难度
24	两两交换链表中的节点	[✓]	递归 链表
1721	交换链表中的节点		链表 双指针
2074	反转偶数长度组的节点		链表