本文概览本文以LeetCode经典题目K 个一组翻转链表为例从普通反转链表入手重点讲解如何按组截取、如何保证前后链表不断开以及如何用 NPC 三指针法完成局部链表反转一、题目二、题目分析给定链表的头节点head每k个节点一组进行翻转返回修改后的链表。如果节点总数不是k的整数倍最后剩余不足k个节点保持原有顺序目标每次翻转链表中的一小段并保证整条链表不断开核心难点这题不是单纯反转整条链表而是反转链表中的某一段。每反转一组之后还要把这一组重新接回前后链表中主要难点有两个如何反转当前这 k 个节点部分反转后如何保证前面的链表和后面的链表不丢失思路概览Java实现代码如下public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } // 创建哑节点 ListNode dummy new ListNode(0, head); // 上一组的尾节点初始为dummy ListNode prevGroupEnd dummy; while (true) { // 检查是否有足够的k个节点 ListNode groupEnd prevGroupEnd; for (int i 0; i k; i) { groupEnd groupEnd.next; if (groupEnd null) { return dummy.next; } } // 记录下一组的头节点当前组的尾节点的下一个节点 ListNode nextGroupHead groupEnd.next; // 记录当前组的头节点 ListNode curGroupHead prevGroupEnd.next; // 反转链表之后返回新的头节点将上一组的尾节点指向新的头节点 prevGroupEnd.next reverse(curGroupHead, nextGroupHead); // 将上一组的尾节点更新为当前组的头节点当前组反转后的尾节点 prevGroupEnd curGroupHead; } } private ListNode reverse(ListNode curGroupHead, ListNode groupEnd) { // 记录当前反转后的组的最左节点 ListNode prev groupEnd; // 记录当前组准备要反转的节点 ListNode curr curGroupHead; // 准备反转的节点不等于组的尾节点就说明还有节点没插完 while (curr ! groupEnd) { ListNode nxt curr.next; // ① 提前存住下一个要处理的节点 curr.next prev; // ② 头插当前节点挂到前面 prev curr; // ③ 更新最左节点当前节点成为新的最左节点 curr nxt; // ④ 更新当前节点处理下一个节点 } return prev; // 最左节点就是新的头节点返回新的头节点 }思路简要说明按组处理每次先检查后面是否还有 k 个节点不足 k 个就直接结束记录前后连接点prevGroupEnd记录上一组的尾节点nextGroupHead记录下一组的头节点防止链表断开局部反转对[curGroupHead, nextGroupHead)这段链表进行反转反转后返回新的头节点接回链表上一组尾节点连接到当前组反转后的新头节点当前组原头节点变成新尾节点作为下一轮的prevGroupEnd三、思路详解从普通反转链表入手前面做过反转链表以后这题的核心并不陌生。普通反转链表就是把整条链表从1 → 2 → 3 → 4变成4 → 3 → 2 → 1而这道题只是把整条链表反转变成了每 k 个节点反转一次原链表1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 k 3 结果 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8也就是说我们每次只反转一小段链表不足 k 个节点的部分保持不变这题真正难在哪里思路本身不难每次找到 k 个节点然后反转它们真正难的是代码实现因为局部反转会带来两个问题问题一当前组反转后前面的链表怎么接回来比如dummy → 1 → 2 → 3 → 4 → 5如果要反转1 → 2 → 3反转后应该变成dummy → 3 → 2 → 1 → 4 → 5这意味着上一组的尾节点dummy必须指向当前组反转后的新头节点 3所以我们需要prevGroupEnd记录上一组的尾节点问题二当前组反转后后面的链表不能丢失反转1 → 2 → 3时后面的4 → 5必须保留下来并且反转后要接到 1 后面3 → 2 → 1 → 4 → 5所以我们需要提前记录下一组的头节点nextGroupHead也就是当前组尾节点的下一个节点每一组需要记录哪些指针每次处理一组时我们需要几个关键指针prevGroupEnd上一组的尾节点用来连接当前组反转后的新头节点groupEnd当前组的尾节点用来判断是否有 k 个节点nextGroupHead下一组的头节点也就是当前组反转时的终止位置curGroupHead当前组的头节点反转后会变成当前组的尾节点图示如下prevGroupEnd ↓ dummy → 1 → 2 → 3 → 4 → 5 → 6 ↑ ↑ ↑ curGroupHead groupEnd nextGroupHead 当前要反转的范围是[curGroupHead, nextGroupHead) 也就是1 → 2 → 3为什么反转范围写成[curGroupHead, nextGroupHead)因为nextGroupHead是下一组的头节点它不能被反转只是作为当前组反转的终止边界如何检查是否还有 k 个节点每一轮开始时先让groupEnd从prevGroupEnd出发向后走 k 步ListNode groupEnd prevGroupEnd; for (int i 0; i k; i) { groupEnd groupEnd.next; if (groupEnd null) { return dummy.next; } }如果走不到 k 步说明剩余节点不足 k 个直接返回结果。因为题目要求不足 k 个节点保持原顺序NPC 三指针反转法这里的reverse方法使用的是 NPC 三指针法nxtnext提前保存当前节点的下一个节点防止断链prevpre已经反转部分的头节点currcur当前准备反转的节点代码如下private ListNode reverse(ListNode curGroupHead, ListNode groupEnd) { ListNode prev groupEnd; ListNode curr curGroupHead; while (curr ! groupEnd) { ListNode nxt curr.next; curr.next prev; prev curr; curr nxt; } return prev; }注意这里的prev初始值不是null而是groupEnd也就是下一组的头节点为什么因为我们不是反转整条链表而是反转某一段链表。当前组反转后原来的头节点会变成当前组的尾节点它的next应该指向下一组的头节点所以一开始让ListNode prev groupEnd;这样反转过程中当前组的尾部会天然接到下一组的头节点不会断链图示理解局部反转过程以当前组1 → 2 → 3下一组头节点为4为例反转前 prevGroupEnd → 1 → 2 → 3 → 4 → 5 ↑ ↑ curGroupHead groupEnd参数这里实际是nextGroupHead4 reverse(1, 4)初始化prev 4 curr 1 4 → 5 ↑ prev 1 → 2 → 3 → 4 → 5 ↑ curr第1轮处理节点 1nxt curr.next; // nxt 2 curr.next prev; // 1 → 4 prev curr; // prev 1 curr nxt; // curr 2结果1 → 4 → 5 ↑ prev 2 → 3 → 4 → 5 ↑ curr此时节点 1 已经变成反转后这组的尾节点并且自然接上了下一组的头节点 4第2轮处理节点 2nxt curr.next; // nxt 3 curr.next prev; // 2 → 1 prev curr; // prev 2 curr nxt; // curr 3结果2 → 1 → 4 → 5 ↑ prev 3 → 4 → 5 ↑ curr第3轮处理节点 3nxt curr.next; // nxt 4 curr.next prev; // 3 → 2 prev curr; // prev 3 curr nxt; // curr 4结果3 → 2 → 1 → 4 → 5 ↑ prev curr 4循环结束此时prev就是当前组反转后的新头节点 3返回prev反转后如何接回上一组reverse(curGroupHead, nextGroupHead)返回的是当前组反转后的新头节点所以prevGroupEnd.next reverse(curGroupHead, nextGroupHead);例如当前组1 → 2 → 3反转后变成3 → 2 → 1 → 4返回的就是 3于是dummy → 3 → 2 → 1 → 4 → 5反转完成后原来的当前组头节点curGroupHead已经变成了当前组的尾节点所以要更新prevGroupEnd curGroupHead;这样下一轮反转时prevGroupEnd就指向上一组的尾节点了完整例子以1 → 2 → 3 → 4 → 5 → 6 → 7 → 8k 3为例第一组1,2,3反转前dummy → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 反转后dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8 prevGroupEnd 更新为 1第二组4,5,6反转前dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8 反转后dummy → 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8 prevGroupEnd 更新为 4剩余7,8 不足 3 个不足 k 个保持不变 最终结果3 → 2 → 1 → 6 → 5 → 4 → 7 → 8时间复杂度O(n)每个节点只被处理一次空间复杂度O(1)只使用常数个指针变量
Hot 100 --- K 个一组翻转链表
本文概览本文以LeetCode经典题目K 个一组翻转链表为例从普通反转链表入手重点讲解如何按组截取、如何保证前后链表不断开以及如何用 NPC 三指针法完成局部链表反转一、题目二、题目分析给定链表的头节点head每k个节点一组进行翻转返回修改后的链表。如果节点总数不是k的整数倍最后剩余不足k个节点保持原有顺序目标每次翻转链表中的一小段并保证整条链表不断开核心难点这题不是单纯反转整条链表而是反转链表中的某一段。每反转一组之后还要把这一组重新接回前后链表中主要难点有两个如何反转当前这 k 个节点部分反转后如何保证前面的链表和后面的链表不丢失思路概览Java实现代码如下public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } // 创建哑节点 ListNode dummy new ListNode(0, head); // 上一组的尾节点初始为dummy ListNode prevGroupEnd dummy; while (true) { // 检查是否有足够的k个节点 ListNode groupEnd prevGroupEnd; for (int i 0; i k; i) { groupEnd groupEnd.next; if (groupEnd null) { return dummy.next; } } // 记录下一组的头节点当前组的尾节点的下一个节点 ListNode nextGroupHead groupEnd.next; // 记录当前组的头节点 ListNode curGroupHead prevGroupEnd.next; // 反转链表之后返回新的头节点将上一组的尾节点指向新的头节点 prevGroupEnd.next reverse(curGroupHead, nextGroupHead); // 将上一组的尾节点更新为当前组的头节点当前组反转后的尾节点 prevGroupEnd curGroupHead; } } private ListNode reverse(ListNode curGroupHead, ListNode groupEnd) { // 记录当前反转后的组的最左节点 ListNode prev groupEnd; // 记录当前组准备要反转的节点 ListNode curr curGroupHead; // 准备反转的节点不等于组的尾节点就说明还有节点没插完 while (curr ! groupEnd) { ListNode nxt curr.next; // ① 提前存住下一个要处理的节点 curr.next prev; // ② 头插当前节点挂到前面 prev curr; // ③ 更新最左节点当前节点成为新的最左节点 curr nxt; // ④ 更新当前节点处理下一个节点 } return prev; // 最左节点就是新的头节点返回新的头节点 }思路简要说明按组处理每次先检查后面是否还有 k 个节点不足 k 个就直接结束记录前后连接点prevGroupEnd记录上一组的尾节点nextGroupHead记录下一组的头节点防止链表断开局部反转对[curGroupHead, nextGroupHead)这段链表进行反转反转后返回新的头节点接回链表上一组尾节点连接到当前组反转后的新头节点当前组原头节点变成新尾节点作为下一轮的prevGroupEnd三、思路详解从普通反转链表入手前面做过反转链表以后这题的核心并不陌生。普通反转链表就是把整条链表从1 → 2 → 3 → 4变成4 → 3 → 2 → 1而这道题只是把整条链表反转变成了每 k 个节点反转一次原链表1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 k 3 结果 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8也就是说我们每次只反转一小段链表不足 k 个节点的部分保持不变这题真正难在哪里思路本身不难每次找到 k 个节点然后反转它们真正难的是代码实现因为局部反转会带来两个问题问题一当前组反转后前面的链表怎么接回来比如dummy → 1 → 2 → 3 → 4 → 5如果要反转1 → 2 → 3反转后应该变成dummy → 3 → 2 → 1 → 4 → 5这意味着上一组的尾节点dummy必须指向当前组反转后的新头节点 3所以我们需要prevGroupEnd记录上一组的尾节点问题二当前组反转后后面的链表不能丢失反转1 → 2 → 3时后面的4 → 5必须保留下来并且反转后要接到 1 后面3 → 2 → 1 → 4 → 5所以我们需要提前记录下一组的头节点nextGroupHead也就是当前组尾节点的下一个节点每一组需要记录哪些指针每次处理一组时我们需要几个关键指针prevGroupEnd上一组的尾节点用来连接当前组反转后的新头节点groupEnd当前组的尾节点用来判断是否有 k 个节点nextGroupHead下一组的头节点也就是当前组反转时的终止位置curGroupHead当前组的头节点反转后会变成当前组的尾节点图示如下prevGroupEnd ↓ dummy → 1 → 2 → 3 → 4 → 5 → 6 ↑ ↑ ↑ curGroupHead groupEnd nextGroupHead 当前要反转的范围是[curGroupHead, nextGroupHead) 也就是1 → 2 → 3为什么反转范围写成[curGroupHead, nextGroupHead)因为nextGroupHead是下一组的头节点它不能被反转只是作为当前组反转的终止边界如何检查是否还有 k 个节点每一轮开始时先让groupEnd从prevGroupEnd出发向后走 k 步ListNode groupEnd prevGroupEnd; for (int i 0; i k; i) { groupEnd groupEnd.next; if (groupEnd null) { return dummy.next; } }如果走不到 k 步说明剩余节点不足 k 个直接返回结果。因为题目要求不足 k 个节点保持原顺序NPC 三指针反转法这里的reverse方法使用的是 NPC 三指针法nxtnext提前保存当前节点的下一个节点防止断链prevpre已经反转部分的头节点currcur当前准备反转的节点代码如下private ListNode reverse(ListNode curGroupHead, ListNode groupEnd) { ListNode prev groupEnd; ListNode curr curGroupHead; while (curr ! groupEnd) { ListNode nxt curr.next; curr.next prev; prev curr; curr nxt; } return prev; }注意这里的prev初始值不是null而是groupEnd也就是下一组的头节点为什么因为我们不是反转整条链表而是反转某一段链表。当前组反转后原来的头节点会变成当前组的尾节点它的next应该指向下一组的头节点所以一开始让ListNode prev groupEnd;这样反转过程中当前组的尾部会天然接到下一组的头节点不会断链图示理解局部反转过程以当前组1 → 2 → 3下一组头节点为4为例反转前 prevGroupEnd → 1 → 2 → 3 → 4 → 5 ↑ ↑ curGroupHead groupEnd参数这里实际是nextGroupHead4 reverse(1, 4)初始化prev 4 curr 1 4 → 5 ↑ prev 1 → 2 → 3 → 4 → 5 ↑ curr第1轮处理节点 1nxt curr.next; // nxt 2 curr.next prev; // 1 → 4 prev curr; // prev 1 curr nxt; // curr 2结果1 → 4 → 5 ↑ prev 2 → 3 → 4 → 5 ↑ curr此时节点 1 已经变成反转后这组的尾节点并且自然接上了下一组的头节点 4第2轮处理节点 2nxt curr.next; // nxt 3 curr.next prev; // 2 → 1 prev curr; // prev 2 curr nxt; // curr 3结果2 → 1 → 4 → 5 ↑ prev 3 → 4 → 5 ↑ curr第3轮处理节点 3nxt curr.next; // nxt 4 curr.next prev; // 3 → 2 prev curr; // prev 3 curr nxt; // curr 4结果3 → 2 → 1 → 4 → 5 ↑ prev curr 4循环结束此时prev就是当前组反转后的新头节点 3返回prev反转后如何接回上一组reverse(curGroupHead, nextGroupHead)返回的是当前组反转后的新头节点所以prevGroupEnd.next reverse(curGroupHead, nextGroupHead);例如当前组1 → 2 → 3反转后变成3 → 2 → 1 → 4返回的就是 3于是dummy → 3 → 2 → 1 → 4 → 5反转完成后原来的当前组头节点curGroupHead已经变成了当前组的尾节点所以要更新prevGroupEnd curGroupHead;这样下一轮反转时prevGroupEnd就指向上一组的尾节点了完整例子以1 → 2 → 3 → 4 → 5 → 6 → 7 → 8k 3为例第一组1,2,3反转前dummy → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 反转后dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8 prevGroupEnd 更新为 1第二组4,5,6反转前dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8 反转后dummy → 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8 prevGroupEnd 更新为 4剩余7,8 不足 3 个不足 k 个保持不变 最终结果3 → 2 → 1 → 6 → 5 → 4 → 7 → 8时间复杂度O(n)每个节点只被处理一次空间复杂度O(1)只使用常数个指针变量
