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

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

image.png

分析

  1. K不是固定的,每循环K次,对链表进行一次截取。
  2. 将截取后的链表进行反转,拼接到我们的目标链表中。
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):我们只需要建立常数个变量

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。