写点什么

【LeetCode】K 个一组翻转链表 Java 题解

作者:HQ数字卡
  • 2021 年 11 月 17 日
  • 本文字数:1280 字

    阅读完需:约 4 分钟

题目描述

给你一个链表,每 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]
示例 3:
输入:head = [1,2,3,4,5], k = 1输出:[1,2,3,4,5]
示例 4:
输入:head = [1], k = 1输出:[1]
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法每日一题是链表题目,链表是一种物理存储单元上非连续、非顺序的存储结构。链表的特点是便于插入和删除,时间复杂度是 O(1)。

  • 对于 K 个一组反转题目,我们可以拆分成子问题分别去解决。其中一个子问题是将链表拆分成 K 个一组,对于这个问题,我们采用计数器 i, 在遍历链表的过程中,每次 i++, 同时需要保证 ListNode != null, 当 ListNode == null 的时候,即为循环的终止条件。

  • 另一个子问题是翻转链表。我们分析反转的过程,首先暂存 head.next 节点,然后将 head.next 指向上一个 pre 节点,在更新当前的 pre 节点,逐个反转。具体实现代码如下:具体实现代码如下:

通过代码

/** * 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) {        ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode pre = head;        ListNode end = dummy;
while (end.next != null) { for (int i = 0; i < k && end != null; i++) { end = end.next; }
if (end == null) { break; }
ListNode start = pre.next; ListNode next = end.next; end.next = null; pre.next = reverseList(start);
start.next = next; pre = start; end = pre; }
return dummy.next; } public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr != null) { ListNode nextNode = curr.next; curr.next = pre; pre = curr; curr = nextNode; } return pre; }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n),空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 2 小时前阅读数: 4
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】K 个一组翻转链表Java题解