leetcode[25]-K 个一组翻转链表

题目
给你链表头节点，每K个一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

image.png

分析

K不是固定的，每循环K次，对链表进行一次截取。
将截取后的链表进行反转，拼接到我们的目标链表中。

func reverseKGroup(head *ListNode, k int) *ListNode {
    // 首先，需要一个指针指向头节点，每次指针向前移动k个节点，同时将k个节点进行反转，
    // 并将反转后的链表连接到目标链表的尾部，然后返回目标链表

    // 将目标链表指向头指针链表
    target := &ListNode{Next: head}

    // pre指向head节点，表示前一个节点
    pre := target

    // 移动head指针
    for head != nil {
        // 每k个一组
        // tail指向前节点
        tail := pre
        for i := 0; i < k; i++ {
            // 更新尾节点
            tail = tail.Next
            // 尾节点为空，则直接返回
            if tail == nil {
                return target.Next
            }
        }
        // 此时tail指针指向第k个节点后的节点=，于是我们需要将head，
        // 接下来我们需要将head和tail作为参数对链表进行一次反转

        // 保存截取后的子链表
        next := tail.Next
        // head是反转后的链表的头节点，tail是反转后的链表的尾节点
        head, tail = reverseListNode(head, tail)
        // 将目标链表指向反转后的链表
        pre.Next = head
        // 更新尾节点为截取后的子链表
        tail.Next = next
        // 移动前指针到尾节点
        pre = tail
        // 移动头节点到尾节点下一个节点，开启新的一轮循环
        head = tail.Next
    }
    return target.Next
}

func reverseListNode(head *ListNode, tail *ListNode) (*ListNode, *ListNode) {
    pre := tail.Next
    p := head
    for pre != tail {
        next := p.Next
        p.Next = pre
        pre = p
        p = next
    }
    return tail, head
}

整个过程细节比较多，主要有两个点，
1）我们定义了target节点，prev节点，tail节点，加上head节点我们得到了完整的链表结构，target节点是我们的目标节点
2）整个过程需要不断更新prev节点指针指向，以及head指针指向，对链表进行更新，从而使得我们的target节点不断更新得到最终链表。

提交测试

62/62 cases passed (8 ms)
Your runtime beats 10.83 % of golang submissions
Your memory usage beats 99.32 % of golang submissions (3.5 MB)

算法时间复杂度为O(N)：每次只进行O(n/k)停留，停留过程只需要经过O(k)的反转操作，结算起来还是O(N)
空间复杂度O(1)：我们只需要建立常数个变量

最后编辑于：2024.07.24 09:28:00