25. Reverse Nodes in k-Group

25. K 个一组翻转链表

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

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

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

示例 1：

img

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

示例 2：

img

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

提示：

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

1. 流程模拟

img

需要使用四个变量记住四个关键节点. 反转链表函数将两节点之间的链表反转.

func reverseKGroup(head *ListNode, k int) *ListNode {
    // 哨兵节点
    dummy := &ListNode{}
    dummy.Next = head
    
    subHead := head // 子链表头节点
    subTail := dummy // 子链表尾节点
    subPrev := dummy // 子链表的前一节点

    for subHead != nil {
        // 移动尾节点
        for i := 0; i < k; i++ {
            subTail = subTail.Next
            // 剩余不满k个 
            if subTail == nil {
                return dummy.Next  
            }
        }

        subNext := subTail.Next // 子链表的下一节点
        // 反转子链表
        subHead, subTail = reverse(subHead, subTail)

        // 连接
        subPrev.Next = subHead
        subTail.Next = subNext

        // 更新操作节点
        subPrev = subTail
        subHead = subTail.Next        
    }

    return dummy.Next
}

func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
    prev := tail.Next 
    cur := head 
    for prev != tail {
        next := cur.Next
        cur.Next = prev

        prev = cur
        cur = next
    }

    return tail, head
}

2. 变形: 不满k个也反转

只需改变尾节点的移动逻辑即可, subTail到达整个链表尾节点则停止移动.

// ...
		for i := 0; i < k; i++ {
            // 不满k个则到尾节点为止
            if subTail.Next == nil {
                break
            }
            subTail = subTail.Next
        }
// ...

Reference

1. https://leetcode.cn/problems/reverse-nodes-in-k-group/solutions/248591/k-ge-yi-zu-fan-zhuan-lian-biao-by-leetcode-solutio/