目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
25-K 个一组翻转链表
访问量:1724
一、题目简介
题目地址:https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
二、解法
关键点:1、使用哨兵减少判断;2、使用数组简单的模拟栈的功能
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ // 思路 p1 从head开始遍历 // p2 每次从p1,开始遍历,用于判断剩下的长度是否大于k, // 如果剩余节点大于 k,即p1于p2之间 一组 // 翻转 p1 到 p2 直接的节点 // p1 设置p2, 重新开始上面遍历 func reverseKGroup(head *ListNode, k int) *ListNode { if k <= 1 { return head } if head == nil || head.Next == nil { return head } p1 := head for p1.Next != nil { var p2 *ListNode if p1 == head { p2 = p1 } else { p2 = p1.Next } // 判断是否还有 k个节点 isExist := false // 如果不足k个节点,直接返回 for i := 1; i < k; i++ { p2 = p2.Next if p2 == nil { isExist = true break } } if isExist { // 剩下节点不足k个节点不需要翻转 break } // 翻转p1 ~ p2 之间的节点 if p1 == head { // 添加一个哨兵 p3 := &ListNode{ Next: p1, } p1 = revertNodes(p3, p2) head = p2 } else { p1 = revertNodes(p1, p2) } } return head } // 翻转 p1.Next 到 p2 直接的节点 // 返回 翻转后的最后一个节点 func revertNodes(p1, p2 *ListNode) *ListNode { p2Next := p2.Next // 基于数组,利用栈的特性实现翻转 nodes := make([]*ListNode, 0) p3 := p1.Next for { nodes = append(nodes, p3) p3 = p3.Next if p3 == p2.Next { break } } nodesLen := len(nodes) for i := nodesLen - 1; i >= 0; i-- { p1.Next = nodes[i] p1 = nodes[i] } p1.Next = p2Next return p1 }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助