K个一组翻转链表(力扣25 困难题)Java

简介: 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

一、题目描述



给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。


k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。


进阶:


你可以设计一个只使用常数额外空间的算法来解决此问题吗?

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


示例 1:

dbe3e63c11974064abf8b379d58fa878.png

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

输出:[2,1,4,3,5]


示例 2:

b1e5321c24394e18a28166a1c1543dcf.png


输入: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]


提示:

列表中节点的数量在范围 sz 内

1 <= sz <= 5000

0 <= Node.val <= 1000

1 <= k <= sz


二、思路讲解


       

本题的思路很简单,难度在于考虑的点很多,容易写出冗长的代码。

     

基本思路就是将k个节点取出来,翻转后,再接入原数组中。


三、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) {
        int len = 0;    //链表长度
        //计算链表长度
        ListNode temp = head;
        while(temp != null){
            len++;
            temp = temp.next;
        }
        int cishu = len / k;    //需要翻转的次数
        //给链表head之前增加一个节点,方便
        ListNode hair = new ListNode(0, head); 
        ListNode pre = hair;    //指向需要翻转的那段链表的前一个节点
        ListNode next;          //指向需要翻转的那段链表的后一个节点
        ListNode tail = pre;    //指向需要翻转的那段链表的末尾
        for(int i=0; i<cishu; i++){ //控制翻转次数
            for(int j=0; j<k; j++){ //末尾节点先找到位置
                tail = tail.next;
            }
            next = tail.next;
            ListNode []nodes = myReverse(head, tail);
            head = nodes[0];
            tail = nodes[1];
            //将翻转后的链表重新接入原链表中
            pre.next = head;
            tail.next = next;
            pre = tail;
            head = tail.next;
        }
        return hair.next;
    }
    //翻转一段链表,传入链表的头指针和尾指针,返回翻转后的链表的头指针和尾指针
    public static ListNode[] myReverse(ListNode head, ListNode tail){
        ListNode next;
        ListNode pre = head;
        ListNode p = head.next;
        while(pre != tail){
            next = p.next;      //保存p节点之后的节点
            p.next = pre;       //保存p节点之后的节点
            pre = p;            //移动两个指针
            p = next;
        }
        return new ListNode[]{tail, head};
    }
}


四、时空复杂度分析



时间复杂度:        O(N)        遍历一次链表

     

空间复杂度:        O(1)

相关文章
|
4月前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
3月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
30 3
|
3月前
【LeetCode】整数翻转
【LeetCode】整数翻转
21 1
|
3月前
|
算法 Java
LeetCode(一)Java
LeetCode(一)Java
|
5月前
|
存储 Java
|
5月前
|
存储 Java
java实现单链表的创建、增、删、改、查
这篇文章详细介绍了Java中如何实现单链表的创建以及对单链表进行增加、删除、修改、查询等操作的方法,并提供了相应的代码示例。
java实现单链表的创建、增、删、改、查
|
5月前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
133 0
|
5月前
|
存储 Java
【Java集合类面试十】、HashMap中的循环链表是如何产生的?
在多线程环境下,HashMap在扩容时如果发生条件竞争,元素的插入顺序可能形成循环链表,导致死循环。
|
5月前
|
存储 Java
java实现双向链表的增删改查
这篇文章展示了如何在Java中实现双向链表的增加、删除、修改和查询操作,并通过代码示例演示了在双向链表中存储和操作学生信息的过程。
|
7月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表