重生北京上大学开网吧做网站的小说,广电基础设施建设官方网站,代码审计wordpress,网站建设与维护试题链表K个节点的组内逆序调整问题
作者#xff1a;Grey
原文地址#xff1a;
博客园#xff1a;链表K个节点的组内逆序调整问题
CSDN#xff1a;链表K个节点的组内逆序调整问题
题目描述
LeetCode 25. Reverse Nodes in k-Group
本题的 follow up 是#xff1a;
Fol…链表K个节点的组内逆序调整问题
作者Grey
原文地址
博客园链表K个节点的组内逆序调整问题
CSDN链表K个节点的组内逆序调整问题
题目描述
LeetCode 25. Reverse Nodes in k-Group
本题的 follow up 是
Follow-up: Can you solve the problem in O(1) extra memory space?即用 O ( 1 ) O(1) O(1)的空间复杂度实现整个算法。
主要思路
本题需要设计两个方法
第一个方法
ListNode getKGroupEnd(ListNode start, int k)该方法表示从链表start位置开始数够k个位置返回k个位置后的那个节点。
比如链表为
...- start - b - c - d - e假设k 3
则表示从start开始数够 3 个所以返回c节点
如果是下述情况
...- start - b - c - null假设k 6
由于start后面不够 6 个节点所以返回null完整代码如下
public static ListNode getKGroupEnd(ListNode start, int k) {while (--k ! 0 start ! null) {start start.next;}return start;
}第二个方法void reverse(ListNode start, ListNode end)表示反转start到end之间的链表。
例如原链表为
....-a-b-c-d-e....假设start a, end d
经过reverse方法会变成
...d-c-b-a-e.....reverse方法也相对比较简单就是链表反转的一种特殊情况实现代码如下:
public static void reverse(ListNode start, ListNode end) {end end.next;ListNode pre null;ListNode cur start;while (cur ! end) {ListNode tmp cur.next;cur.next pre;pre cur;cur tmp;}start.next end;
}有了上述两个方法我们可以比较方便实现原题要求主流程如下
public static ListNode reverseKGroup(ListNode head, int k) {ListNode start head;ListNode end getKGroupEnd(start, k);if (end null) {return head;}// 第一组凑齐了head end;reverse(start, end);// 上一组的结尾节点ListNode lastEnd start;while (lastEnd.next ! null) {start lastEnd.next;end getKGroupEnd(start, k);if (end null) {return head;}reverse(start, end);lastEnd.next end;lastEnd start;}return head;
}整个过程时间复杂度 O ( N ) O(N) O(N)空间复杂度 O ( 1 ) O(1) O(1)。
更多
算法和数据结构学习笔记
算法和数据结构学习代码
参考资料
算法和数据结构体系班-左程云
