题目描述
给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
算法思路
首先,为需要返回的链表设置一个头结点list以及尾节点rear。
然后,使用整数count记录链表的节点个数,每当满足条件count % k == 0
时,翻转这k个节点组成的部分链表。
使用start表示需要翻转的部分链表的第一个节点,用end表示需要翻转的部分链表的最后一个节点。
使用pre表示翻转后的部分链表的第一个节点,采用头插法,翻转部分链表。翻转完毕后,start成为了该部分链表的最后一个节点。
接着,让翻转后的链表成为rear的后继,即rear.next = pre
,然后让rear = start
,并将原链表的下一个节点赋给start,开启新一轮的翻转。
最后,待循环执行完毕后,若链表后面还有不足k个节点,即count % k != 0
,直接让剩余的这部分链表成为rear的后继,即rear = start
。
算法实现
1 | /** |
复杂度分析
时间复杂度:该算法只遍历链表一次,故时间复杂度为O(n)。
空间复杂度:该算法只使用了常数的额外空间,故空间复杂度为O(1)
算法效率
执行用时 : 2 ms, 在Reverse Nodes in k-Group的Java提交中击败了100.00% 的用户
内存消耗 : 37.6 MB, 在Reverse Nodes in k-Group的Java提交中击败了0.93% 的用户