Java关于重排链表详细解析

1.题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

 L0→ L1 → … → Ln-1 → Ln  请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

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

 来源：力扣（LeetCode）

2.解析

将一个链表分为两个子链表，然后将其归并。

我们要先找到链表的中间节点，在中间节点将其断开

然后反转后半链表

再将两个子链表逐个连起来

 将后半链表反转，独立成一个子链表。

最后将两个子链表的节点逐个连接就OK了

3.代码

class Solution {
    public void reorderList(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        //找中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //截断链表
        ListNode cur = slow.next;
        slow.next = null;
        //反转后半链表
        ListNode node = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = node;
            node = cur;
            cur = curNext;
        }
        //合并
        ListNode prev = head;
        ListNode l1 = node;
        while (l1 != null) {
            ListNode next1 = prev.next;
            ListNode next2 = l1.next;
            prev.next = l1;
            l1.next = next1;
            prev = next1;
            l1 = next2;
        }

    }
}

到此这篇关于Java关于重排链表详细解析的文章就介绍到这了,更多相关Java 重排链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • java单链表使用总结

    链表的概念: 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列节点(链表中的每一个元素称为节点)组成,节点可以在运行时动态生成.每个节点包含两个部分:一个是存储数据元素的数据域,另一个是存储下一个节点地址的指针域.相对于线性表顺序结构,操作复杂.由于不必按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O

  • Java复杂链表的复制详解

    Java复杂链表的复制详解

    目录 1.题目 2.解法 2.1 拼接+拆分 3.代码 1.题目 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 2.解法 2.1 拼接+拆分 首先我们逐个将节点复制并且和原来的链表连起

  • Java实现单链表的操作

    Java实现单链表的操作

    本文实例为大家分享了Java实现单链表的基本操作,供大家参考,具体内容如下 顺序表:物理上逻辑上都连续:链表:物理上不一定连续,逻辑上一定连续的. 链表的概念及结构 概念:连表示一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的. 8种链表结构: 单项.双向带头.不带头循环.非循环 主要的三种链表: 无头单项非循环链表.带头循环单链表.不带头双向循环链表 代码实现 1. 接口定义 package com.github.linked.Impl; publ

  • Java 详解如何从尾到头打印链表

    Java 详解如何从尾到头打印链表

    目录 1.题目 2.解法 2.1栈 2.2递归 3.复杂度 3.1栈 3.2递归 1.题目 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回). 题目来源:力扣(LeetCode) 2.解法 2.1栈 栈的特点是先进后出,所以我们创建一个栈,逐个将节点压入栈内,然后建立一个数组,将栈内的节点数值逐个弹出 class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> stack = new

  • Java实现链表数据结构的方法

    Java实现链表数据结构的方法

    什么是链表? 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的.每一个链表都包含多个节点,节点又包含两个部分,一个是数据域(储存节点含有的信息),一个是引用域(储存下一个节点或者上一个节点的地址). 链表的理解示意图: 链表的特点是什么? 获取数据麻烦,需要遍历查找,比数组慢方便插入.删除 简单的链表的实现原理 创建一个节点类,其中节点类包含两个部分,第一个是数据域(你到时候要往节点里面储存的信息),第二个是引用域(相当于指针,单向链表有一个指

  • Java实现无头双向链表操作

    Java实现无头双向链表操作

    本文实例为大家分享了Java实现无头双向链表的具体代码,供大家参考,具体内容如下 无头双向链表的结构: 代码分析 节点结构 class Node {     private int data;     private Node next;     private Node prev;     public Node(int data) {         this.data = data;         this.prev = null;         this.next = null;  

  • Java数据结构与算法学习之双向链表

    Java数据结构与算法学习之双向链表

    目录 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 2.双向链表的头结点 3.总代码 双向链表中的指定文件插入元素  1.插入的为第一个位置 2.其他位置插入 总代码 双向链表的删除 1.删除第一个元素 2.删除其他位置元素 总代码 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 代码实现 //双向链表的结点,包含一个数据域,两个指针域 typedef struct DoublyNode { ElementType date; //数据域 struct

  • 带你了解Java数据结构和算法之链表

    带你了解Java数据结构和算法之链表

    目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结 前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会

  • Java 详解分析链表的中间节点

    Java 详解分析链表的中间节点

    目录 1.题目描述 2.解法 3.复杂度 1.题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点. 如果有两个中间结点,则返回第二个中间结点. 题目来源:力扣(LeetCode) 2.解法 定义一个快指针 fast 和一个慢指针 slow :fast 走两步, slow 走一步,当 fas t走到尽头时, slow 就刚好在中间节点.因为 fast 比slow 多走一半路程 class Solution { public ListNode middleNode(ListNod

  • Java关于重排链表详细解析

    Java关于重排链表详细解析

    1.题目 给定一个单链表 L 的头节点 head ,单链表 L 表示为:  L0→ L1 → - → Ln-1 → Ln  请将其重新排列后变为: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → - 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换.  来源:力扣(LeetCode) 2.解析 将一个链表分为两个子链表,然后将其归并. 我们要先找到链表的中间节点,在中间节点将其断开 然后反转后半链表 再将两个子链表逐个连起来  将后半链表反转,独立成一个子链表. 最

  • Java Stream.reduce()用法详细解析

    目录 基本使用 额外举例 并行读流 处理异常 复杂对象的处理 总结 在学习这个函数的用法之前,我们要先知道这个函数参数的意义 基本使用 先举一个简单的例子: 算法题:Words题目描述每个句子由多个单词组成,句子中的每个单词的长度都可能不一样,我们假设每个单词的长度Ni为该单词的重量,你需要做的就是给出整个句子的平均重量V. 解答要求时间限制:1000ms, 内存限制:100MB输入输入只有一行,包含一个字符串S(长度不会超过100),代表整个句子,句子中只包含大小写的英文字母,每个单词之间有一

  • Java线程的相关方法详细解析

    start()  启动线程方法 run()  调用start()方法时,真正执行的就是该方法的方法体 sleep()  让当前线程睡眠,睡眠到期自动苏醒,并进入可运行状态,而不是运行状态 yield() 暂停当前正在执行的线程对象,JVM线程调度程序基于优先级的抢先机制调用其他优先级高的线程,优先级的取值范围1 (Thread.MIN_PRIORITY) -- 10( Thread.MAX_PRIORITY),创建线程默认是5 (NORM_PRIORITY) setPriority(int ne

  • Java 负载均衡算法作用详细解析

    Java 负载均衡算法作用详细解析

    目录 前言 轮询算法 随机算法 加权随机算法 加权轮询算法 源地址hash算法 最小请求数算法 前言 负载均衡在Java领域中有着广泛深入的应用,不管是大名鼎鼎的nginx,还是微服务治理组件如dubbo,feign等,负载均衡的算法在其中都有着实际的使用 负载均衡的核心思想在于其底层的算法思想,比如大家熟知的算法有 轮询,随机,最小连接,加权轮询等,在现实中不管怎么配置,都离不开其算法的核心原理,下面将结合实际代码对常用的负载均衡算法做一些全面的总结. 轮询算法 轮询即排好队,一个接一个的轮着

  • java中Optional的使用详细解析

    java中Optional的使用详细解析

    Optional的使用详解 1.Optional介绍 Optional 类是一个可以为null的容器对象.如果值存在则isPresent()方法会返回true,调用get()方法会返回该对象. Optional 是个容器:它可以保存类型T的值,或者仅仅保存null.Optional提供很多有用的方法,这样我们就不用显式进行空值检测. Optional 类的引入很好的解决空指针异常. 2.构建Optional 构建一个Optional对象:方法有:empty( ).of( ).ofNullable

  • Java 泛型考古 泛型擦除 包装类详细解析

    Java 泛型考古 泛型擦除 包装类详细解析

    目录 一. 什么是泛型 二. 为什么要有泛型 ? 示例 三.泛型考古 四.泛型擦除 五.包装类 六.装箱拆箱 一. 什么是泛型 泛型(generic type)其本质是将类型参数化,也就是说所操作的数据类型被指定为一个参数这种参数类型可以用在类.接口和方法的创建中,分别称为泛型类.泛型接口.泛型方法. 二. 为什么要有泛型 ? 之前写过MyArrayList顺序表,这个类当时自己在实现的时候只能用一种类型来表示,也就是用的时候自己实现的MyArrayList只能应用于一种类型,要想应用于其他类型

  • Java详细解析==和equals的区别

    目录 1.== 解析 2.equals 方法解析 3.equals方法具有以下特性 1.== 解析 == 常用于相同的基本数据类型之间的比较,也可用于相同类型的对象之间的比较: 如果 == 比较的是基本数据类型,那么比较的是两个基本数据类型的值是否相等: 如果 == 是比较的两个对象,那么比较的是两个对象的引用,那么就是比较两个对象的引用是否相等,也就是判断两个对象是否指向了同一块内存区域: 2.equals 方法解析 equals 方法主要用于两个对象之间,检测一个对象是否等于另一个对象. 我

  • 关于java中@Async异步调用详细解析附代码

    目录 前言 1. @Async讲解 2. 用法 2.1 同步调用 2.2 异步调用 3. 自定义线程池 前言 异步调用与同步调用 同步调用:顺序执行,通过调用返回结果再次执行下一个调用 异步调用:通过调用,无需等待返回结果,执行下一个调用 1. @Async讲解 其@Async的注解代码如下: @Target({ElementType.TYPE, ElementType.METHOD}) @Retention(RetentionPolicy.RUNTIME) @Documented public

  • Java详细解析下拉菜单和弹出菜单的使用

    Java详细解析下拉菜单和弹出菜单的使用

    目录 Swing菜单组件 下拉式菜单介绍 下拉式菜单的三个组件 JMenuBar(菜单栏) JMenu(菜单) JMenuItem(菜单项) 下拉式菜单的创建与使用 创建和添加下拉式菜单的一般步骤 弹出式菜单介绍 弹出式菜单的创建与使用 小结 Swing菜单组件 下拉式菜单介绍 创建一个下拉式菜单,需要三个组件,JmenuBar(菜单栏),Jmenu(菜单),Jmenultem(菜单项). 下拉式菜单的三个组件 JMenuBar(菜单栏) 表示一个水平的菜单栏,用来管理菜单,不参与同用户的交互式

  • Java static关键字详细解析

    目录 static目的 static范围 静态(static)修饰 静态变量 静态方法 静态代码块 静态类 static变量存储在方法区(Method Area) static目的 java中的static关键字主要用于内存管理. static范围 使用范围:java static关键字可以用在变量.方法.代码块和嵌套类中. 作用范围:static关键字属于类,而不是类的实例. 静态(static)修饰 变量.方法:称为类变量/方法.静态变量/方法:修饰变量或方法,表示这个变量/方法属于这个类,

随机推荐