【算法 -- LeetCode】（025） K 个一组翻转链表

news/2024/10/19 6:22:53/

在这里插入图片描述

1、题目

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

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

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
在这里插入图片描述

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：
在这里插入图片描述

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

题目链接：https://leetcode.cn/problems/reverse-nodes-in-k-group

2、图解

题目要求在一个链表中以 k 个链表节点为单位进行反转，什么意思呢？

你可以想象把一个很长的链表分成很多个小链表，每一份的长度都是 k (最后一份的长度如果小于 k 则不需要反转)，然后对每个小链表进行反转，最后将所有反转后的小链表按之前的顺序拼接在一起。

其实 链表的题目并不需要特别强的逻辑推理，它主要强调细节实现，难也是难在细节实现上面，虽然大致的方向知道，但是很可能写着写着就会乱。

所以这个题目实现的时候要把握住几个要点：

第一，在反转子链表的时候，上一个子链表的尾必须知道
第二，下一个子链表的头也必须知道
第三，当前反转的链表的头尾都必须知道

3、Java 示例代码

/*** 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) {if (head == null || head.next == null || k <= 1) {return head;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode pointer = dummy;while (pointer != null) {// 记录上一个子链表的尾ListNode lastGroup = pointer;int i = 0;            for (; i < k; ++i) {pointer = pointer.next;if (pointer == null) {break;}}// 如果当前子链表的节点数满足 k, 就进行反转// 反之，说明程序到尾了，节点数不够，不用反转if (i == k) {// 记录下一个子链表的头ListNode nextGroup = pointer.next;// 反转当前子链表，reverse 函数返回反转后子链表的头ListNode reversedList = reverse(lastGroup.next, nextGroup);// lastGroup 是上一个子链表的尾，其 next 指向当前反转子链表的头// 但是因为当前链表已经被反转，所以它指向的是反转后的链表的尾pointer = lastGroup.next;// 将上一个链表的尾连向反转后链表的头lastGroup.next = reversedList;// 当前反转后的链表的尾连向下一个子链表的头pointer.next = nextGroup;}}return dummy.next;}private ListNode reverse(ListNode head, ListNode tail) {if (head == null || head.next == null) {return head;}ListNode prev = null, temp = null;while ((head != null) && (head != tail)) {temp = head.next;head.next = prev;prev = head;head = temp;}return prev;}
}