前置知识
- 数据结构-链表
- 反转部分链表
- 算法题的手写栈使用
难度：
- 初阶：使用容器， 难度中等。
- 进阶：纯coding修改指针 ，难度中等，虽然leetcode是困难题。不过更加注重细节。
题目：反转 k 组中的节点
给定一个单链表的头节点head, 实现一个调整单链表的函数， 要求每k个节点之间逆序， 如果不够k个节点，那么不调整。
输入： head = [1,2,3,4,5], k = 2输出： [2,1,4,3,5]
其中， [1,2]为一组，[3,4]为一组，5不足则不调整。[1,2]逆序[2,1], [3,4]逆序[4,3]。
细节处理：
- 第一组逆转时， 整个链表的头节点从原来的1改成了2， 涉及
换头逻辑处理。 题目也要求返回新链表的头节点。需要处理。 -
1 <= k <= n <= 5000, 力扣给定范围。考虑特殊数据的处理。 k<2的链表是不需要处理的。因为k<=0视为无效，k==1是对单个节点进行逆序，没有意义。因此，排除了1的处理。 - 由于我们逆序的是某个链表的局部， 这就涉及对整体链表与局部修改连接的维护。具体看code。
解法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;
}
-
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指向节点就是修改后的新头节点。 -
cur指向的就是当前要入栈的节点，压栈 stack[size++] = cur;cur还充当外部循环遍历链表的作用。 -
next: 修改局部链表尾节点的后继, 当发生逆序过程时，next指向那一组尾节点的后继。比如[1,2]逆序时，next指向2的后继3。因为只有进入循环， next始终是cur.next。 -
prev：修改局部链表头节点的前驱， 第一组修改时为null,所以初始化为null,后续组的前驱节点交给reversePart函数返回值维护。 -
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(n) O(n)
空间复杂度: O ( k ) O(k) 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;
}
每日两题结束。