当前位置：首页 > news >正文

Leecode刷题之路第25天之K个一组翻转链表

news 2024/10/22 11:32:27

题目出处

25-K个一组翻转链表-题目出处

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

在这里插入图片描述

提示：链表中的节点数目为 n1 <= k <= n <= 50000 <= Node.val <= 1000进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

个人解法

思路：

todo

代码示例：（Java）

todo

复杂度分析

todo

官方解法

25-K个一组翻转链表-官方解法

方法1：模拟

思路：

在这里插入图片描述

代码示例：（Java）

public class Solution1 {@Datapublic 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 ListNode reverseKGroup(ListNode head, int k) {ListNode hair = new ListNode(0);hair.next = head;ListNode pre = hair;while (head != null) {ListNode tail = pre;// 查看剩余部分长度是否大于等于 kfor (int i = 0; i < k; ++i) {tail = tail.next;if (tail == null) {return hair.next;}}ListNode nex = tail.next;ListNode[] reverse = myReverse(head, tail);head = reverse[0];tail = reverse[1];// 把子链表重新接回原链表pre.next = head;tail.next = nex;pre = tail;head = tail.next;}return hair.next;}public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev = tail.next;ListNode p = head;while (prev != tail) {ListNode nex = p.next;p.next = prev;prev = p;p = nex;}return new ListNode[]{tail, head};}}