题目描述
给你链表的头节点 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
代码及注释
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// reverseKGroup 函数用于反转链表中的每 k 个节点。
func reverseKGroup(head *ListNode, k int) *ListNode {
// 创建一个哑节点作为链表的起始节点
dummy := &ListNode{
Next: head,
}
// 初始化 pre 节点为哑节点
pre := dummy
// 遍历链表,直到 head 为 nil
for head != nil {
// 初始化 tail 节点为 pre
tail := pre
// 找到需要反转的 k 个节点的尾节点
for i := 0; i < k; i++ {
tail = tail.Next
// 如果剩余节点数少于 k,则直接返回结果
if tail == nil {
return dummy.Next
}
}
// 记录下一个节点
next := tail.Next
// 调用 reverseAll 函数反转 k 个节点
head, tail = reverseAll(head, tail)
// 将反转后的链表连接到原链表中
pre.Next = head
tail.Next = next
// 更新 head 和 pre
head = tail.Next
pre = tail
}
// 返回反转后的链表
return dummy.Next
}
// reverseAll 函数用于反转从 head 到 tail 的链表
func reverseAll(head, tail *ListNode) (*ListNode, *ListNode) {
// 初始化 pre 为 tail 的下一个节点
pre := tail.Next
// 初始化 cur 为 head
cur := head
// 遍历 head 到 tail 之间的节点,并进行反转
for pre != tail {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 返回反转后的头尾节点
return tail, head
}
代码解释
reverseKGroup 函数:
-
初始化哑节点和 pre 节点:
dummy := &ListNode{ Next: head, } pre := dummy
- 创建一个哑节点作为链表的起始节点,这样可以简化后续的操作。
- 初始化
pre
节点为哑节点。
-
遍历链表:
for head != nil {
- 使用
for
循环遍历链表,直到head
为nil
。
- 使用
-
找到需要反转的 k 个节点的尾节点:
tail := pre for i := 0; i < k; i++ { tail = tail.Next if tail == nil { return dummy.Next } }
- 初始化
tail
节点为pre
。 - 使用
for
循环找到需要反转的k
个节点的尾节点。
- 初始化
-
记录下一个节点和反转链表:
next := tail.Next head, tail = reverseAll(head, tail)
- 记录
tail
的下一个节点。 - 调用
reverseAll
函数反转k
个节点。
- 记录
-
连接反转后的链表到原链表中:
pre.Next = head tail.Next = next
- 将反转后的链表连接到原链表中。
- 更新
head
和pre
。
-
返回反转后的链表:
return dummy.Next
- 返回反转后的链表。
reverseAll 函数:
-
初始化 pre 和 cur:
pre := tail.Next cur := head
- 初始化
pre
为tail
的下一个节点。 - 初始化
cur
为head
。
- 初始化
-
反转链表:
for pre != tail { next := cur.Next cur.Next = pre pre = cur cur = next }
- 使用
for
循环遍历head
到tail
之间的节点,并进行反转。
- 使用
-
返回反转后的头尾节点:
return tail, head
- 返回反转后的头尾节点。