算法题-Leetcode- K 个一组翻转链表 ( 常数额外空间)
前言
这是一道看似简单，但又是细节搞死人的题目。
题目链接:K 个一组翻转链表
思路
该题如果用 栈或递归来做，那必定是一个简单的问题了，其重点在于题目要求使用常数级的额外空间。
首先获取链表的长度 length
关于K值，当 其 k == 1 或者 k > length 情况，显然都无需翻转
定义一个 cur,last 分别指向当前节点，以及上个节点，pref 指向的是上个k链中的最后一个节点.startNode指向的是每个k链原排序中的第一个节点。
当前节点不为 k 链中最后一个节点时，将当前节点的next指向 last 节点，实现 k 链内的翻转
当前节点为 K 链中最后一个节点时
(1)将当前节点的next 指向last 节点. 该节点也是 k 链的头部，因此将 上个K链中的最后一个节点 pref.next = cur;（如果pref==null.说明此时处于第一个 k链，当前节点即是 Head节点）。
(2)更新 pref 指向该k链中最后一个节点，即是startNode.
(3)在 下个k链的头部节点未确定下，pref.next 先指向接下来的第一个节点。目的是防止接下的不满足k个情况而导致其头部没有前缀
(4)startNode 则更新指向下个未翻转k链的第一个节点。
代码
public ListNode reverseKGroup(ListNode head, int k) { ListNode pref = null; ListNode cur,last, startNode,t; int length = getLength(head); int endIndex = length - length%k -1; if (k == 1 || k > length) return head; int i = 0; cur = head; startNode = head; last = null; while (cur != null) { if (i > endIndex){ break; } //末尾 if (i % k == k - 1) { t = cur.next; if (pref == null) {//说明是首部 head = cur;//当前作为head } else { pref.next = cur; } cur.next = last;//访问上次 cur = t; pref = startNode;// 上一轮的开始节点，也是上一轮的尾部，其变为了下个k长链表的前缀 pref.next = cur;// 将其指向为变化的下个k链表的头部，目的是防止接下的不满足k个情况而导致其头部没有前缀 startNode = cur;//新一轮k } else { t = cur.next; cur.next = last; last = cur; cur = t; } i++; } return head; } public int getLength(ListNode head){ int size = 0 ; while (head!=null){ head= head.next; size++; } return size; }
作者：陈序猿_Android
链接：https://juejin.cn/post/7011467117648150558