首页 > 其他分享 >leetcode148:排序链表

leetcode148:排序链表

时间:2022-08-25 18:22:48浏览次数:76  
标签:head ListNode leetcode148 next 链表 temp2 return 排序

package com.mxnet;

public class Solution148 {

    public static void main(String[] args) {

    }

    /**
     * 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
     * @param head
     * @return
     * 思路:
     * 1. 使用归并排序的思路,即依次二分链表再合并
     * 2. 递归的将链表二分,递归结束的条件为子链表只剩下一个元素或者子链表为空
     * 3. 对于而二分的子链表,使用链表的从小到达排序算法将其合并
     * 4. 最后则得到完整升序的链表
     */
    public ListNode sortList(ListNode head) {
        return sortList(head,null);
    }

    /**
     * 递归将一条链表进行排序
     * @param head
     * @param tail
     * @return
     */
    public ListNode sortList(ListNode head, ListNode tail) {
        //递归结束条件:链表中没有元素或者只有一个元素
        if (head == null){
            return head;
        }
        if (head.next == tail){
            head.next = null;
            return head;
        }
        //创建快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //快指针移动一次,慢指针移动两次,当快指针到达链表末尾时,慢指针刚好到链表中间
        while (fast != tail){
            fast = fast.next;
            slow = slow.next;
            if (fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        //递归排序并组合
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode merge = merge(list1, list2);
        return merge;
    }

    /**
     * 将两条链表由小到大合并
     * @param head1 链表1
     * @param head2 链表2
     * @return
     * 思路:
     * 1. 创建一条新链表用于保存排好序的链表
     * 2. 循环将两条链表最前边的值进行比较,每次取出最小的挂在到新链表上
     * 3. 若两条链表长度不一致,则在循环结束后将较长链表后半部分挂在新链表后边
     */
    public ListNode merge(ListNode head1, ListNode head2){
        //创建新链表保存排好序的链表
        ListNode dummyHead = new ListNode();
        //创建辅助链表
        ListNode temp = dummyHead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        //每次通过节点大小取出一个节点链接到新链表后面
        while (temp1 != null && temp2 != null){
            if (temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else if (temp1.val > temp2.val){
                temp.next = temp2;
                temp2 = temp2.next;
            }
            //temp辅助指针后移
            temp = temp.next;
        }
        //当其中一条链表为空,另一条不为空时,将不为空链表连接到后面
        if (temp1 != null){
            temp.next = temp1;
        }else if (temp2 != null){
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

标签:head,ListNode,leetcode148,next,链表,temp2,return,排序
From: https://www.cnblogs.com/mx-info/p/16625298.html

相关文章

  • 堆排序
    packagecom.lianzhu.filemanage.utils;importjava.util.Stack;/***栈排序*@description:栈的特性:先进后出如空数组【】*@step1:有一串数字4,8,7,9,2,6......
  • el-tree只能同级拖拽排序
    <el-tree:data="treeData"node-key="id"draggable:allow-drop="allowDrop"@node-drop="handleDrop"></el-tree>主要是用到了allow-drop这个方法,然后去......
  • 2022-8-25 剑指offer-字典树-每日一题-二分/排序
    剑指OfferII063.替换单词难度中等25收藏分享切换为英文接收动态反馈在英语中,有一个叫做 词根(root) 的概念,它可以跟着其他一些词组成另一个较长的单词——我......
  • js 对象数组根据对象的某一个属性值来进行数据排序
    1、根据id值从小到大排序//模拟数据varlist=[{"id":5,"name":"小明","age":5},{"id":2,"name":"小红","age":12},{"id":3,"name":......
  • Java-Java集合排序
    一、ListMap排序修订记录版本是否发布2020-01-25v1.0是一、ListMap排序Java中list里面存放map,根据map中的某一个或多个字段进行排序importjava.u......
  • Js文件名 排序
    压缩版functionarraySortByName(list){if(list===undefined||list===null){return[]}list.sort((a,b)=>{letstrA=a,strB=b;if(strA===undefined||strA===null||strA===......
  • P3201 [HNOI2009] 梦幻布丁 将颜色x变成颜色y 问总共有多少种颜色 启发式合并+链表
    https://www.luogu.com.cn/problem/P3201题目描述nn 个布丁摆成一行,进行 mm 次操作。每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。......
  • 什么是双向链表?双向链表的操作封装实现(增删改查)?
    什么是双向链表?双向链表既可以从头遍历到尾,又可以从尾遍历到头也就是链表相连的过程是双向的.那么它的实现原理,你能猜到吗?一个节点既有向前连接的引用,也......
  • 合并两条有序链表
     用JavaScript实现:constlink1=newLinkedList()link1.append(1)link1.append(3)link1.append(4)link1.append(6)li......
  • 双链表和循环链表
    一、结构体定义1.双链表typedefstructDLNode{ intdata; structDLNode*prior,*next;}DLNode;2.循环链表//同双链表二、操作1.尾插法建立双链表voidcreat......