25. K 个一组翻转链表
链表中多个子链表的翻转
25.题目链接-来源:力扣(LeetCode)
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
进阶:
你可以设计一个只使用常数额外空间的算法来解决此问题吗?
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
思路:
此题是上一题的一般情况,我们可以沿用其框架,即对于一段长度为 k 的待处理节点,用 preCur 指向该段的前驱,用 curFront 标记本段的起始节点,然后对 preCur 之后的 k 个节点,我们提取一个 reverse() 方法单独处理对其的翻转操作,返回反转以后的头结点。由于我们要避免处理长度不足 k 的末尾段,在进行 reverse() 操作之前,我们要从 preCur 之后数出 k 个节点,若计数未满即至表尾,则表示已经无需操作,跳出循环。
每次循环末尾,我们需要更新 preCur 的信息,preCur 作为下一段节点的前驱,其应该指向当前段完成 reverse() 以后的最末节点,也就是本轮循环一开始的起始节点 curFront。
记得用 哑节点 dummy 帮助我们简化判断逻辑,完成后,返回 dummy.next即可。
时间复杂度:O(n)
空间复杂度:O(1)
实现:
1 | class Solution { |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.