【LeetCode】K 个一组翻转链表 Java 题解
题目描述
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
进阶:
你可以设计一个只使用常数额外空间的算法来解决此问题吗?你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
复制代码
思路分析
今天的算法每日一题是链表题目,链表是一种物理存储单元上非连续、非顺序的存储结构。链表的特点是便于插入和删除,时间复杂度是 O(1)。
对于 K 个一组反转题目,我们可以拆分成子问题分别去解决。其中一个子问题是将链表拆分成 K 个一组,对于这个问题,我们采用计数器 i, 在遍历链表的过程中,每次 i++, 同时需要保证 ListNode != null, 当 ListNode == null 的时候,即为循环的终止条件。
另一个子问题是翻转链表。我们分析反转的过程,首先暂存 head.next 节点,然后将 head.next 指向上一个 pre 节点,在更新当前的 pre 节点,逐个反转。具体实现代码如下:具体实现代码如下:
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/a5320aa385deca08a2f2d601e】。文章转载请联系作者。
评论