网站的建设分析及意义,wordpress归档插件,专业建站分销商城,小程序开发一个多少钱文章目录 1. 题目2. 思路及代码实现#xff08;Python#xff09;2.1 模拟 1. 题目
给你链表的头节点 h e a d head head #xff0c;每 k k k 个节点一组进行翻转#xff0c;请你返回修改后的链表。 k k k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节… 文章目录 1. 题目2. 思路及代码实现Python2.1 模拟 1. 题目
给你链表的头节点 h e a d head head 每 k k k 个节点一组进行翻转请你返回修改后的链表。 k k k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k k k 的整数倍那么请将最后剩余的节点保持原有顺序。不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
是否可以设计一个只用 O ( 1 ) O(1) O(1) 额外内存空间的算法解决此问题
示例 1 输入 h e a d [ 1 , 2 , 3 , 4 , 5 ] , k 2 head [1,2,3,4,5], k 2 head[1,2,3,4,5],k2 输出 [ 2 , 1 , 4 , 3 , 5 ] [2,1,4,3,5] [2,1,4,3,5]
示例 2
输入 h e a d [ 1 , 2 , 3 , 4 , 5 ] , k 3 head [1,2,3,4,5], k 3 head[1,2,3,4,5],k3 输出 [ 3 , 2 , 1 , 4 , 5 ] [3,2,1,4,5] [3,2,1,4,5] 提示
链表中的节点数目为 n n n 1 k n 5000 1 k n 5000 1kn5000 0 N o d e . v a l 1000 0 Node.val 1000 0Node.val1000
2. 思路及代码实现Python
2.1 模拟
我们需要把链表节点按照 k k k 个一组分组所以可以使用一个指针 h e a d head head 依次指向每组的头节点。这个指针每次向前移动 k k k 步直至链表结尾。对于每个分组我们先判断它的长度是否大于等于 k k k。若是我们就翻转这部分链表否则不需要翻转。
在翻转子链表的时候我们不仅需要子链表头节点 h e a d head head还需要有 h e a d head head 的上一个节点 p r e pre pre以便翻转完后把子链表再接回 p r e pre pre。但是对于第一个子链表它的头节点 h e a d head head 前面是没有节点 p r e pre pre 的这时候可以新建一个节点把它接到链表的头部让它作为 p r e pre pre 的初始值这样 h e a d head head 前面就有了一个节点我们就可以避开链表头部的边界条件。反复移动指针 h e a d head head 与 p r e pre pre对 h e a d head head 所指向的子链表进行翻转直到结尾我们就得到了答案。
该算法的时间复杂度为 O ( n ) O(n) O(n) n n n 为链表长度空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution:# 翻转一个子链表并且返回新的头与尾def reverse(self, head: ListNode, tail: ListNode):prev tail.nextp headwhile prev ! tail:nex p.nextp.next prevprev pp nexreturn tail, headdef reverseKGroup(self, head: ListNode, k: int) - ListNode:hair ListNode(0)hair.next headpre hairwhile head:tail pre# 查看剩余部分长度是否大于等于 kfor i in range(k):tail tail.nextif not tail:return hair.nextnex tail.nexthead, tail self.reverse(head, tail)# 把子链表重新接回原链表pre.next headtail.next nexpre tailhead tail.nextreturn hair.next执行用时44 ms 消耗内存17.11 MB
题解来源力扣官方题解
