网站架构计划书四川建设学习网

前置知识

• 数据结构-链表
• 反转部分链表
• 算法题的手写栈使用

难度：

• 初阶：使用容器， 难度中等。
• 进阶：纯coding修改指针 ，难度中等，虽然leetcode是困难题。不过更加注重细节。

题目：反转 k 组中的节点

解法1：使用栈这个容器

事先声明， 这里采用的是全局静态数组充当栈的写法， 读者可根据需求自行改写成Java，C++内置栈的写法。
讲解在代码下面。

//提交代码， 将类名ReverseGroup -> Solution
public class ReverseGroup {//题目给定k最大5000，那么5001肯定足够了。 实测1201也可以public static int MAX = 5001;//类静态数组充当栈public static ListNode[] stack = new ListNode[MAX];//记录栈的大小， size == 0意味栈空。public static int size;//主方法public ListNode reverseKGroup(ListNode head, int k) {//排除无效数据if(k < 2) {return head;}//重置size,防止被上组数据污染， 实现空间复用。size = 0;return f(head,k);//调用辅助方法}/*** * @param head 原链表头节点* @param k 每k个逆序* @return 返回新链表的头节点*/private ListNode f(ListNode head, int k) {ListNode newHead = head, cur = head, prev = null, next = null;while(cur != null) {next = cur.next;//压栈stack[size++] = cur;while(size==k) {//满足则执行逆序prev = reversePart(prev,next);//调整newHead为修改后链表的头节点。newHead = newHead == head?cur: newHead;}cur = next;}return newHead;}/*** * @param left 修改局部链表头节点的前驱* @param right	修改局部链表尾节点的后继* @return 返回下一对修改局部链表的前驱节点。*/private ListNode reversePart(ListNode left, ListNode right) {ListNode cur = stack[--size];if(left != null) {left.next = cur;}ListNode next = null;while(size > 0) {next = stack[--size];cur.next = next;cur = next;}cur.next = right;return cur;}
}

private ListNode f(ListNode head, int k) {ListNode newHead = head, cur = head, prev = 					null, next = null;while(cur != null) {next = cur.next;//压栈stack[size++] = cur;while(size==k) {//满足则执行逆序prev = reversePart(prev,next);//调整newHead为修改后链表的头节点。newHead = newHead == head?cur: newHead;}cur = next;}return newHead;}

1. newHead:修改后链表的新头节点。从逻辑上有两种可能， 如果发生第一组的调整， 那么newHead一定不是原先的head, 那么你可以看到内层while循环内部newHead = newHead == head?cur: newHead;, 就是第一组逆序， newHead应该指向cur的节点。
   比如，[1,2,3,4,5], k=2, cur在应该指向2这个节点，刚好第一组逆序[2,1,3,4,5]， cur指向节点就是修改后的新头节点。
2. cur指向的就是当前要入栈的节点，压栈 stack[size++] = cur;cur还充当外部循环遍历链表的作用。
3. next: 修改局部链表尾节点的后继, 当发生逆序过程时，next指向那一组尾节点的后继。比如[1,2]逆序时，next指向2的后继3。因为只有进入循环， next始终是cur.next。
4. prev：修改局部链表头节点的前驱， 第一组修改时为null,所以初始化为null,后续组的前驱节点交给reversePart函数返回值维护。
5. size==k，当前栈大小满足k时需要逆序这组。reversePart(prev,next)这个函数，接受这组的前驱和后继，比如[1,2,3,4,5], k=2, 先逆序[1,2]，就需要传入null前驱，3后继。因为函数内部逻辑要维护局部修改和整体的连接。reversePart(prev,next),这个函数还需要返回下一组（如果不存在那么用不上了）的前驱节点。比如[2,1,3,4,5]完成了1，2之间的逆序，那么还要返回下一对[3,4]的前驱1。那么下一次调用就传入1前驱和5后继来逆序3，4。

private ListNode reversePart(ListNode left, ListNode right) {ListNode cur = stack[--size];if(left != null) {left.next = cur;}ListNode next = null;while(size > 0) {next = stack[--size];cur.next = next;cur = next;}cur.next = right;return cur;}

• 先出栈， 出栈节点就是局部链表的头结点， left（不为空）连接该节点。
• 循环出栈连接逻辑
• 最后出栈的结点连接后继right。
• 返回下一组的前驱节点就是当前cur的节点。自行画图理解。
  
  时间复杂度:$O(n)$
  空间复杂度:$O(k)$

解法2:原链表调整

//提交时，注意修改函数名public ListNode reverseKGroup1(ListNode head, int k) {// 特殊输入判断if (k < 2) {return head;}ListNode cur = head, start = null, prev = null, next = null;int count = 1;// 计数变量。while (cur != null) {next = cur.next;// 后继始终跟着循环更新。if (count == k) {start = prev == null ? head : prev.next;// 获得当前逆序对开始节点head = prev == null ? cur : head;// 第一组逆序需要修改头节点reversePart2(prev, start, cur, next);// (prev,next),[start,end]prev = start;// 更新前驱范围count = 0;// 重置}++count;// 自增cur = next;// cur跟着next。}return head;// head指向的更新后的头节点或者原先的头节点。}private void reversePart2(ListNode left, ListNode start, ListNode end,ListNode right) {//反转部分链表一样的逻辑 ListNode prev = start,next = null, cur = start.next;while(cur != right){next = cur.next;cur.next = prev;prev = cur;cur = next;}if(left!=null) {left.next = end;}start.next = right;}

每日两题结束。