K 个一组翻转链表（leetcode 25）

​

1.问题描述

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

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

注意：

• 只能使用常数的额外空间。
• 不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例：

给你这个链表：1->2->3->4->5

当 k = 1 时，应当返回: 1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

2.难度等级

hard。

3.热门指数

★★★★☆

出题公司：阿里，腾讯，百度，字节。

4.解题思路

思路

这道题是反转链表（leetcode 206）的进阶版本，可以看成是有 n 个长度为 k 的链表进行反转然后拼接在一起。

所以，反转链表是基础，需要先了解一下反转链表的实现。

反转链表步骤如下：

1. 使用一个全局变量保留每个结点的前驱结点，记为 pre。
2. 从第一个节点开始遍历，临时保存当前结点的 next 结点，变更当前结点的 next 指针指向前驱结点 pre。
3. 当前结点作为前驱结点赋给 pre，当前结点的 next 结点赋值给当前结点，继续遍历，直到为 NULL。

下面是 Golang 的一个实现示例。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
    return pre
}

对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表连接，以及子链表的尾部与下一个子链表连接。

然后就是遍历链表，按照反转每个分组后，将分组连接起来。

具体做法如下：

1. 先分组，用一个 head 和 tail 分别表示当前分组的起始与结束结点。
2. 反转分组（不足 k 个节点不需要反转）。
3. 将反转后的当前分组连接到前一个分组的结束结点 pre。

反转第一个分组时，可以虚构一个 pre 结点，这样就不用做边界判断，简化代码。

那么一个链表的结构可以拆解成下面的样子。

反复移动指针 head 与 pre，对 head 所指向的子链表进行翻转，直到结尾，我们就得到了答案。

复杂度分析

时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在 O(⌊n/k⌋) 个结点上停留，每次停留需要进行一次 O(k) 的翻转操作。

空间复杂度：O(1)，我们只需要建立常数个变量。

5.实现示例

下面以 Golang 为例，给出实现示例。

因为反转的是分组而不是整个链表，所以反转子链表需要稍微改动一下。

// myReverse 反转分组，返回反转后的首尾结点。
func myReverse(head, tail *ListNode) (*ListNode, *ListNode) {
    pre := tail.Next
    cur := head
    for pre != tail {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return tail, head
}

给定一个链表分组，即给定首位结点。反转后 head 与 tail 的下一个结点连接起来。

接下来就是将循环按照分组反转，然后将反转后的分组与前一个分组连接起来。

func reverseKGroup(head *ListNode, k int) *ListNode {
	hair := &ListNode{Next: head}

	// 反转后链表的最后一个结点
	pre := hair

	for head != nil {
		tail := head
		count := 1
		for ; count < k; count++ {
			if tail.Next == nil {
				break
			}
			tail = tail.Next
		}
		// 分组长度不足 k 不反转。
		if count < k {
			pre.Next = head
			return hair.Next
		}

		next := tail.Next
		head, tail = reverseList(head, tail)
		pre.Next = head
		pre = tail
		head = next
	}
	return hair.Next
}