题目描述#

给你一个链表头节点 head，要求每 k 个节点作为一组进行翻转，并返回处理后的新链表。

如果链表最后剩下的节点数量不足 k 个，那么这一段保持原来的顺序不动。题目还特别要求，不能只交换节点里的值，而是要真正调整链表节点之间的连接关系。

思路#

这份代码依然先用了链表题里很常见的哑节点 dummy。不过这里的 dummy 不只是为了方便处理头节点变化，它还会在每一轮翻转结束后移动到当前这一组的尾部，作为下一组操作时的“前一个节点”。

外层循环每次先检查从 dummy 开始往后是否还能走满 k 个节点。这里通过 tail 向后移动 k 次来判断，如果中途遇到 nil，说明剩余节点数不足 k，那就直接返回答案，不再继续翻转。

确认当前这一组长度足够之后，真正的翻转过程没有额外开辟数组或递归，而是连续做 k-1 次头插。此时 cur 一直指向这一组原本的第一个节点。每次把 cur.Next 这个节点摘下来，插到 dummy.Next 前面，于是这一组的头部不断前移，而 cur 会自然留在这组翻转后链表的尾部。

一组翻完以后，让 dummy = cur，也就是把分组前驱移动到这一组的新尾部；再让 cur = cur.Next，开始处理下一组。整个过程里每个节点只会被常数次操作，因此时间复杂度是 O(n)，额外空间复杂度是 O(1)。

代码#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy.Next
	ans := dummy

	for {
		tail := dummy
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return ans.Next
			}
		}

		for i := 0; i < k-1; i++ {
			next := cur.Next
			cur.Next = cur.Next.Next
			next.Next = dummy.Next
			dummy.Next = next
		}
		dummy = cur
		cur = cur.Next
	}
	return ans.Next
}