25. K 个一组翻转链表

题目

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

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

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

难度：🌟🌟🌟🌟🌟

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

题解

这题非常容易迷失在众多指针变量之中，需要经常回顾学习。
思路：

1. 遍历链表，计算出链表长度；
2. 根据长度和 k，计算出需要翻转的子链表数量；
3. 针对每个子链表做翻转，需要注意的是 next.Next = prev.Next，即下一个节点指向的是子链表当前头节点。
4. 子链表翻转结束后，需要对 curr 和 prev 节点重新定向。

代码实现

func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Val: -1}
	dummy.Next = head
	length := 0 // 记录链表节点数
	for head != nil {
		length++
		head = head.Next
	}
	// 计算需要反转的子链表个数
	prev := dummy
	curr := dummy.Next
	for i := 0; i < length/k; i++ {
		for i := 0; i < k-1; i++ {
			next := curr.Next   // 下一个节点
			second := next.Next // 下两个节点
			curr.Next = second
			next.Next = prev.Next // 指向链表头节点
			prev.Next = next      // 更新链表头节点
		}
		prev = curr // 重新定位新的 prev 和 curr 指针
		curr = prev.Next
	}
	return dummy.Next
}