【力扣面试经典150题】（链表）K 个一组翻转链表

题目描述

力扣原文链接

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
请添加图片描述
提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：
你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
       	// here is your code 
    }
}

解题过程

解题思路

拿到的题目以后，应该尽量根据已知条件、函数的入参和返回值抓住变与不变的量、考虑边界条件、加之常用算法手段，如递归、迭代、双指针、回溯、分治、动态规划等等，从而创造一条完整链路，再考虑时间复杂度和空间复杂度的限制，问题得解。

回到本题，函数入参是一个自定义的ListNode，以及指定的（小于ListNode长度的）正整数用以翻转子链表，最终将新链表返回。所以核心问题有两点：

函数入参指定的链表是否存在一个或者多个长度为K的子链表？
如果存在长度为K的子链表，如何实现这个不断重复的翻转子链表的工作？

接下来把代码要实现的逻辑完整地梳理一遍：

针对以上的两个问题，我们最少要进行一次O(n) 时间复杂度的链表遍历，来确定是否存在合理值K。如果不存在直接返回原链表，因为无需翻转。这是最简单的情况。如果存在合理值K，那么怎么在O(1)空间复杂度的情况下保证子链表的翻转？以及翻转后与旧链表首尾节点的组装？

用一个简单实例说明：
假设链表为 1 -> 2 -> 3 ，K = 2，那么自然会脱口而出，2 -> 1 -> 3，这样看起来是不是很简单呢？
实际上处理过程同上面分析的一样，先判断是否含有K长度子链表，链表长度为3，K为2，当然符合条件，再把K长度子链表 1 -> 2 翻转成 2 -> 1，问题得以解决。

增加虚拟节点

通常地，在解决链表相关问题的时候，习惯性地在给定的链表头加一个节点，由于与题目无关，是我们虚构用来方便计算处理边界条件的，则把它称之为“虚拟节点”。⚠️注意，后面涉及链表相关的问题会常用到虚拟节点。

为了便于理解，现在以链表 1 -> 2 ->3 为例，画图说明：
请添加图片描述
这里我们将原来链表 1- >2- >3 加上了一个虚拟节点，变成了链表 -1 -> 1 -> 2 -> 3

至于为什么要加这个虚拟节点，下文在遍历链表的时候大有用处，我们会详细的说，现在只需要知道虚拟节点这个概念即可。

判断是否存在长度为K的子链表

回到实际问题，仍以链表 1 -> 2 ->3 为例，下图所示，每一个节点都有两个属性

val 当前节点值
next 下个节点
上图标注的整个链表，下文统一用head表示，head是从题目中函数入参拿到的哦

public ListNode reverseKGroup(ListNode head, int k)

首先我们在链表头部加上一个虚拟节点，并声明两个指针 prev 和 last 用来限定K长度子链表的边界。

请添加图片描述

因为我们在入参的head上加了头部的虚拟节点，又加了两个指针，因此我们重新定义个新的dummy链表。

新的dummy链表 -1 -> 1 -> 2 ->3 ，并附加了两个指针 last 和 prev。

//模拟代码
//声明新的dummy链表，比之前的head链表多加了一个虚拟节点，值为-1，指向head
ListNode dummy = new ListNode(-1, head);
//在dummy链表上声明last指针，注意这里没有开辟新的空间
ListNode prev = dummy;
//注意，以上两行代码可以简写，与操作8大基本类型数据的声明是一样的道理，刚接触链表的同学可能看着有点懵，需要细心体会
ListNode dummy = new ListNode(-1, head), prev = dummy;
//在dummy链表上声明prev指针，注意这里没有开辟新的空间
ListNode last = prev;

现在通过移动last指针，移动的长度就是K，所以会有这样的写法：

//模拟代码
for（int i = 0；i < k;i++）{
	//循环K次，每次移动last指针到下一个节点，因为是从虚拟节点开始移动，所以第一次移动后last一定指向dummy的第一个节点。
	last = last.next;
	//移动完要判断下一个节点是否为null，如果为null说明K循环未结束，而当前节点是末尾节点了，说明不足K个节点。直接返回dummy.next即可。
    if (last == null) {
		return dummy.next;
	}
}

通过K次循环last指针，判断dummy链表是否存在合理值K，直至last 为null
请添加图片描述

翻转长度为K的子链表

接着上面的实例，我们假设K=2，那么dummy链表的第一次K循环结束应该是这样的：
请添加图片描述

也就是说我们找到了符合K长度的子链表，接下来需要开始对子链表进行翻转了。

增加虚拟节点的好处
还记得前面我们买了一个伏笔吧！那就是为什么要在head原始链表头上加一个虚拟节点。看到这里我想你应该明白了，那就是

翻转后的K长子链表需要与旧链表进行缝合，那么就需要知道旧链表的被切割处的节点位置，如果正好是前K个链表，那么翻转后只有尾部需要缝合，前面是没有节点的，难道要在翻转前单独判断无头有尾的特殊情况吗？而在head前面加了虚拟节点则正好解决了这个问题，无论K子链表在dummy哪里，一定都是与旧链表相连的、有头有尾的子链表。

请添加图片描述

如果不存在K长子链表，则直接返回第1个节点就可以了，因为后面的节点会跟着第一个节点，这等于是对于入参head没有操作直接返回了。如果存在K长子链表，翻转后，那么从1到K已经进行了翻转，无论后面又翻转了多少个K子节点，返回的头节点就是K。所以两种情况又要单独判断了。但是加上虚拟节点，无论是否翻转，只需要返回dummy.next即可。

接下来我们看具体翻转K子链表的过程。思考为什么经过翻转后，仍只需要返回dummy.next？（不翻转可以理解，就是dummy.next）

首先要考虑翻转的子链表的起始节点和末尾节点。末尾节点就是last，起始节点应该是prev.next ,因为是动态变化的，需要新加一个指针，姑且称之为curr（意为当前节点），所以K长子链表长度应该从curr到last。

//这里curr的取值不能为 dummy.next，因为prev和curr是随着多个K长子链表动态变化的，而dummy则是一个固定的链表。
ListNode curr = prev.next;

请添加图片描述

确定了K长子链表，现在对子链表进行翻转，并将翻转后的片段拼接回dummy。
由于K长可变，试想若是存在合理值K=100，那么翻转一次吗？所以翻转的次数也是需要根据K长动态变化的。

// 比如当前假设情况，K=2 ，那么只需要循环一次即可。因为循环一次，翻转了2个节点。同理多个节点道理如此。
for (int i = 0; i < k - 1; i++) {

}

翻转实际上就是从K长度子链表的第一个节点curr与下一个节点next进行交换，直至交换到last结束。由于curr会不断在循环后刷新，所以next节点也是随curr节点动态变化的。

请添加图片描述

 ListNode next = curr.next;

现在我们要做的事情是交换curr节点与next节点，并保证交换后节点与dummy前后开口正确缝合。

首先切断curr与next的关联关系，让curr直接跳过next指向next的下一个节点。

//原来curr与next相连，现在这个操作相当于把curr的下个节点跳过了next节点，给到了next下一个节点。
curr.next = next.next;

请添加图片描述

将prev节点（K长子链表的头节点）的下一个节点也指向next的下一个节点。

//切断原来next的下一个节点的关联关系，因为上一步进行了1 -> 3 关联, 3节点无需多一个重复被指向，3节点必须是来自于curr的指向。所以把next节点重定向到prev后面。
next.next = prev.next;

请添加图片描述

将prev节点（K长子链表的头节点）重定向到next节点即可

prev.next = next;

请添加图片描述

将prev（K长子链表的头节点）指向下一轮要进行的K长翻转的头节点处

上面步骤实现了从curr到last的K长一次翻转动作，由于K长子链表需要不断在dummy中遍历寻找是否存在多个K，所以下一次循环K2的时候我们需要将K2的头节点指针重新定位。

//curr一定是K长子链表最末尾的一个节点，所以将prev指针移动到curr节点。
prev = curr;

第二次K循环由于last指针需要移动两次，但是节点3的next为空，所以直接返回prev.next了。

代码梳理

完整代码实现

 	public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head), prev = dummy;
        while (true) {
            // 检查剩余节点是否有k个，不足则返回
            ListNode last = prev;
            for (int i = 0; i < k; i++) {
                last = last.next;
                if (last == null) {
                    return dummy.next;
                }
            }
            // 翻转k个节点
            ListNode curr = prev.next, next;
            for (int i = 0; i < k - 1; i++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
        }
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1,new ListNode(2,new ListNode(3)));
        ListNode listNode = reverseKGroup(list1, 2);
        //链表遍历
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }