LeetCode-热题100：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

代码及注释

/**
 * 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 函数：

1. 初始化哑节点和 pre 节点：

   dummy := &ListNode{
       Next: head,
   }
   pre := dummy
   

   • 创建一个哑节点作为链表的起始节点，这样可以简化后续的操作。
   • 初始化 pre 节点为哑节点。

2. 遍历链表：

   for head != nil {
   

   • 使用 for 循环遍历链表，直到 head 为 nil。

3. 找到需要反转的 k 个节点的尾节点：

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

   • 初始化 tail 节点为 pre。
   • 使用 for 循环找到需要反转的 k 个节点的尾节点。

4. 记录下一个节点和反转链表：

   next := tail.Next
   head, tail = reverseAll(head, tail)
   

   • 记录 tail 的下一个节点。
   • 调用 reverseAll 函数反转 k 个节点。

5. 连接反转后的链表到原链表中：

   pre.Next = head
   tail.Next = next
   

   • 将反转后的链表连接到原链表中。
   • 更新 head 和 pre。

6. 返回反转后的链表：

   return dummy.Next
   

   • 返回反转后的链表。

reverseAll 函数：

1. 初始化 pre 和 cur：

   pre := tail.Next
   cur := head
   

   • 初始化 pre 为 tail 的下一个节点。
   • 初始化 cur 为 head。

2. 反转链表：

   for pre != tail {
       next := cur.Next
       cur.Next = pre
       pre = cur
       cur = next
   }
   

   • 使用 for 循环遍历 head 到 tail 之间的节点，并进行反转。

3. 返回反转后的头尾节点：

   return tail, head
   

   • 返回反转后的头尾节点。