leetcode24.25翻转链表讲解

K个一组翻转链表题目描述给你链表的头节点head每k个节点一组进行翻转请你返回修改后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。示例1输入head [1,2,3,4,5], k 2输出[2,1,4,3,5]示例2输入head [1,2,3,4,5], k 3输出[3,2,1,4,5]提示:链表中的节点数目为n1kn50000 Node.val 1000解题思路preNonedummyListNode(nexthead)p0dummy curp0.next这道题其实跟上一篇文章的类似就是多了需要计算链表的长度需要K个K个地进行翻转whilenk:n-kfor_inrange(k):k2这里进行2次循环现在是第1次 nxtcur.nextcur.nextpre precur curnxt完成第1次循环后:pre1cur2节点1已经反转成功。for_inrange(k):k2这里进行2次循环现在是第2次 nxtcur.nextcur.nextpre precur curnxt此时第1组(1,2)已经反转完成但还没有重新接回原链表。nxtp0.next这里先进行保存方便后续每一次需要调换的2个中的第一个数学做下一次循环的P0保存旧头节点是为了后面执行p0nxt进入下一轮。p0.next.nextcur这一句负责把反转后的尾节点接回后面的链表。p0.nextpre p0nxt第1轮完成:成功把1,2反转为2,1并重新接回原链表。接着按照一样的步骤开始第2轮3,4的交换完整代码# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defreverseKGroup(self,head:ListNode|None,k:int)-ListNode|None:curhead n0whilecur:n1curcur.next先计算链表的长度 preNonedummyListNode(nexthead)哨兵节点 p0dummy curp0.nextwhilenk:n-kfor_inrange(k):nxtcur.nextcur.nextpre precur curnxt nxtp0.nextp0.next.nextcur p0.nextpre p0nxtreturndummy.next时间复杂度On第一遍 while cur遍历一遍链表统计总节点数O(n)后面反转循环每个节点只会被反转指针操作一次所有 for 循环加起来全部节点只访问一遍也是 O(n)总O(n)O(n)O(n)空间复杂度是O1只用了若干指针变量所以空间复杂度是O1leetcode24两两交换链表中的节点题目描述给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。输入head [1,2,3,4]输出[2,1,4,3]示例 2输入head []输出[]示例 3输入head [1]输出[1]这道题可以看作是上面leetcode25题固定k2完整代码# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defswapPairs(self,head:ListNode|None)-ListNode|None:n0curheadwhilecur:n1curcur.nextdummyListNode(nexthead)p0dummy preNonecurp0.nextwhilen2:n-2for_inrange(2):nxtcur.nextcur.nextpre precur curnxt nxtp0.nextp0.next.nextcur p0.nextpre p0nxtreturndummy.next时间复杂度On空间复杂度是O1后续会陆续出leetcode的题目解题过程喜欢的小宝可以点赞收藏关注喔