柚子快报邀请码778899分享：K 个一组翻转链表
实现链表分组反转
一、原题
给你链表的头节点 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]来源：力扣（LeetCode）链接：https://leetcode.cn/problems/reverse-nodes-in-k-group
二、解法
1、分析
本题需要实现组内反转，如果不够一组，就不进行反转首先设置链表头，可以先确定是否能找到组内尾节点，找不到直接返回，找到的话，直接设置该节点为头（因为反转后，尾巴就变成了开头），然后进行组内反转，并连接下一组的头节点，到此已经完成了第一步，即设置头，并且完成第一组反转；进行第二组操作，还是先找组内尾结点，然后组内反转，并连接下一组的头节点，进行第三组操作…依次这样操作,直到没有下一组，直接返回
2、解答
题中使用的链表结构
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
代码实现
public class ReverseKGroup {
/**
* 假设链表为1-2-3-4-5，k=2
*/
public static ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
// statr:1-2-3-4-5
// end:2-3-4-5
ListNode start = head;
ListNode end = getLastNode(head, k);
// 表示没找到符合的一组，不反转，直接返回
if (end == null) {
return head;
}
reverse(start, end);
// statr:1-3-4-5
// end:2-1-3-4-5
// 设置头节点：即第一组反转后的头（原组的尾）
head = end;
// 上一组的尾巴
ListNode lastEnd = start;
while (lastEnd.next != null) {
start = lastEnd.next;
end = getLastNode(start, k);
if (end == null) {
return head;
}
reverse(start, end);
lastEnd.next = end; // 上一组连接上当前组
lastEnd = start;
}
return head;
}
/**
* 找到最后一个节点
*/
private static ListNode getLastNode(ListNode head, int k) {
while (--k > 0 && head != null) {
head = head.next;
}
return head;
}
/**
* 开始和结束节点之前翻转，然后连接下一组节点开头
*/
public static void reverse(ListNode start, ListNode end) {
end = end.next; // 结束节点，该节点不需要反转
ListNode cur = start; // 需要一个索引去遍历，start还是指向原来的头，方便最后链接下一组的头
ListNode pre = null;
ListNode next = null;
while (cur != end) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = end;
}
}
Markdown 1770 字数 112 行数 当前行 85, 当前列 54
HTML 1580 字数 93 段落
柚子快报邀请码778899分享：K 个一组翻转链表
发表评论