LeetCode-热题100:148. 排序链表

题目描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

示例 1:

在这里插入图片描述

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

示例 2:

在这里插入图片描述

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

示例 3:

输入: head = []
输出: []

提示:

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

代码及注释

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func sortList(head *ListNode) *ListNode {
    // 边界情况:链表为空或只有一个节点时,直接返回
    if head == nil || head.Next == nil {
        return head
    }

    // 使用快慢指针找到链表的中点
    slow, fast := head, head
    var cur *ListNode
    for fast != nil && fast.Next != nil {
        cur = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 断开链表,将链表分为两部分
    cur.Next = nil

    // 递归地对左右两部分进行排序
    l := sortList(head)
    r := sortList(slow)

    // 合并两个有序链表
    return merge(l, r)
}

func merge(l1 *ListNode, l2 *ListNode) *ListNode {
    // 使用哑节点简化代码
    var dummy = &ListNode{}
    cur := dummy

    // 循环比较两个链表的节点,并将较小的节点连接到新链表中
    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            cur.Next = l2
            l2 = l2.Next
        } else {
            cur.Next = l1
            l1 = l1.Next
        }
        cur = cur.Next
    }

    // 将剩余的节点连接到新链表的末尾
    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }

    // 返回合并后的链表
    return dummy.Next
}

代码解释

sortList 函数

  1. 终止条件

    if head == nil || head.Next == nil {
        return head
    }
    

    当链表为空或只有一个节点时,无需排序,直接返回。

  2. 找到中点

    slow, fast := head, head
    var cur *ListNode
    for fast != nil && fast.Next != nil {
        cur = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    cur.Next = nil
    

    使用快慢指针找到链表的中点,并将链表断开,得到两个子链表 lr

  3. 递归排序

    l := sortList(head)
    r := sortList(slow)
    

    使用递归对左右两个子链表进行排序。

  4. 合并两个排序后的子链表

    return merge(l, r)
    

    调用 merge 函数合并两个排序后的子链表。

merge 函数

  1. 初始化

    var dummy = &ListNode{}
    cur := dummy
    

    使用哑节点 dummycur 指针来合并两个链表。

  2. 比较合并

    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            cur.Next = l2
            l2 = l2.Next
        } else {
            cur.Next = l1
            l1 = l1.Next
        }
        cur = cur.Next
    }
    

    比较 l1l2 的当前节点值,将较小的节点连接到 cur.Next

  3. 处理剩余节点

    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }
    

    将剩余的 l1l2 链接到 cur.Next

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532736.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2017NOIP普及组真题 4. 跳房子

线上OJ&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1417\ 核心思想 首先、本题中提到 “ 至少 要花多少金币改造机器人&#xff0c;能获得 至少 k分 ”。看到这样的话语&#xff0c;基本可以考虑要使用 二分答案。 那么&#xff0c;本题中…

Java快速入门系列-7(测试与调试)

第七章:测试与调试 第7章:测试与调试7.1 单元测试(JUnit)7.1.1 为什么要进行单元测试7.1.2 JUnit基础7.1.3 断言7.1.4 测试套件7.2 集成测试与系统测试7.2.1 集成测试7.2.2 系统测试7.3 调试技巧与工具7.3.1 断点7.3.2 单步执行7.3.3 变量检查7.3.4 条件断点7.3.5 日志记录…

手动实现简易版RPC(一)

手动实现简易版RPC(一) 前言 什么是RPC&#xff1f;它的原理是什么&#xff1f;它有什么特点&#xff1f;如果让你实现一个RPC框架&#xff0c;你会如何是实现&#xff1f;带着这些问题&#xff0c;开始今天的学习。 本文主要介绍RPC概述以及一些关于RPC的知识&#xff0c;为…

网络安全指南:安全访问 Facebook 的技巧

在当今数字化时代&#xff0c;网络安全问题越来越受到人们的关注。尤其是在社交媒体平台上&#xff0c;如 Facebook 这样的巨头&#xff0c;用户的个人信息和隐私更容易受到威胁。为了保护自己的在线安全&#xff0c;我们需要采取一些措施来确保在使用 Facebook 时能够安全可靠…

GET与POST:详述HTTP两大请求方法的语义、数据处理机制、安全特性与适用场景

GET和POST方法在HTTP请求中具有明确的角色分工和特性差异。GET适用于读取操作和不敏感数据的传递&#xff0c;强调可缓存性和安全性&#xff0c;而POST适用于写入操作和敏感数据的提交&#xff0c;提供了更大的数据承载能力和更强的隐私保护。本文详细介绍了GET与POST请求方法的…

利用Sentinel解决雪崩问题(二)隔离和降级

前言&#xff1a; 虽然限流可以尽量避免因高并发而引起的服务故障&#xff0c;但服务还会因为其它原因而故障。而要将这些故障控制在一定范围避免雪崩&#xff0c;就要靠线程隔离(舱壁模式)和熔断降级手段了&#xff0c;不管是线程隔离还是熔断降级&#xff0c;都是对客户端(调…

实战篇05:更新用户基本信息

实战篇05&#xff1a;更新用户基本信息 一、接口信息 1.1 基本信息 请求路径&#xff1a;/user/update 请求方式&#xff1a;PUT 接口描述&#xff1a;该接口用于更新已登录用户的基本信息(除头像和密码) 1.2 请求参数 请求参数格式&#xff1a;application/json 请求参数说…

2024 年 3 月公链行业研报:比特币创新高、Meme 掀热潮、AI 板块露头角

作者&#xff1a;stellafootprint.network 数据来源&#xff1a;Footprint Analytics 公链研究页面 3 月份&#xff0c;加密市场表现强劲&#xff0c;比特币再创历史新高。以太坊价格稳步攀升&#xff0c;而坎昆升级则显著降低了交易成本。Solana 链上 Meme 热潮席卷而来&am…

nandgame中的Memory(内存操作):栈、堆、静态区

Push Memory Push Memory 将内存中的值push到栈内堆栈顶部的值是一个内存地址。从堆栈中弹出地址。获取内存地址的当前内容&#xff0c;并将其推送到堆栈上。POP_A //堆栈顶部的值是一个内存地址。从堆栈中弹出地址。 D *A //获取内存地址的当前内容 PUSH_D //将其推送到…

拉普拉斯IPO丨用创新科技助力中国光伏产业高质量发展

近年来&#xff0c;在“以科技创新引领现代化产业体系建设”的战略指引下&#xff0c;整个光伏行业持续推动技术迭代与生产力升级&#xff0c;朝着更高光电转化效率、更低成本加速迈进。 在此背景下&#xff0c;一批以技术驱动为第一生产力的光伏厂商们&#xff0c;在自身领域…

APP被DDoS攻击时,企业应该如何防护?

某平台遭到分布式拒绝服务攻击&#xff0c;大规模、持续性的攻击&#xff0c;导致平台的APP、网站的部分用户出现间歇性无法登录、加载失败或缓慢等情况。据了解&#xff0c;平台在一个月的时间内陆续遭受到近30次的网络攻击。在这段时间内&#xff0c;平台不断地接收到短时间、…

虚拟货币:数字金融时代的新工具

在数字化时代的到来之后&#xff0c;虚拟货币逐渐成为了一种广为人知的金融工具。虚拟货币是一种数字化的资产&#xff0c;它不像传统货币那样由政府或中央银行发行和监管。相反&#xff0c;虚拟货币通过密码学技术和分布式账本技术来实现去中心化的发行和交易。 虚拟货币的代…

Nodejs 第六十三章(串口技术)

串口介绍 串口技术是一种用于在计算机和外部设备之间进行数据传输的通信技术。它通过串行传输方式将数据逐位地发送和接收。 常见的串口设备有&#xff0c;扫描仪&#xff0c;打印机&#xff0c;传感器&#xff0c;控制器&#xff0c;采集器&#xff0c;电子秤等 SerialPort …

ES6 关于Class类的继承 extends(2024-04-10)

1、简介 类Class 可以通过extends关键字实现继承&#xff0c;让子类继承父类的属性和方法。extends 的写法比 ES5 的原型链继承&#xff0c;要清晰和方便很多。 class Foo {constructor(x, y) {this.x x;this.y y;console.log(父类构造函数)}toString() {return ( this.x …

MyBatis 等类似的 XML 映射文件中,当传入的参数为空字符串时,<if> 标签可能会导致 SQL 语句中的条件判断出现意外结果。

问题 传入的参数为空字符串&#xff0c;但还是根据参数查询了。 原因 在 XML 中使用 标签进行条件判断时&#xff0c;需要明确理解其行为。在 MyBatis 等类似的 XML 映射文件中&#xff0c; 标签通常用于动态拼接 SQL 语句的条件部分。当传入的参数 riskLevel 为空字符串时…

rebase和merge的区别

合并分支用rebase还是merge&#xff1f; 实际开发工作的时候&#xff0c;我们都是在自己的分支开发&#xff0c;然后将自己的分合并到主分支&#xff0c;那合并分支用2种操作&#xff0c;这2种操作有什么区别呢&#xff1f; git上新建一个项目&#xff0c;默认是有master分支…

如何在 YouTube、Medium、Twitter 和 Linkedin 上使用 ChatGPT 赚钱

人工智能SEO&#xff1a;未来内容优化的革命 介绍 在当今的数字时代&#xff0c;利用 ChatGPT 等人工智能工具已经成为在线内容创建和货币化领域的游戏规则改变者。 本指南探讨了如何在 YouTube、Medium、Twitter 和 Linkedin 等各种平台上有效使用 ChatGPT&#xff0c;不仅可以…

猫咪可以每天吃冻干吗?2024最全攻略这几款低调有实力

冻干猫粮近年来逐渐受到养猫人的青睐&#xff0c;其高品质的特性赢得了广大猫主人的认可。对于像我这样的养猫达人来说&#xff0c;早已尝试并认可了冻干喂养。但对于新手来说&#xff0c;他们可能会感到困惑&#xff1a;冻干到底是什么&#xff1f;猫咪可以每天吃冻干吗&#…

Canal的使用场景!!!

1、保持redis和mysql连接的一致性&#xff1a;通常使用延迟双删功能&#xff08;具有弊端&#xff09; 解决方案&#xff1a;可以使用canal监听数据库的变化&#xff08;删改&#xff09;&#xff0c;一旦出现此类操作&#xff0c;立即删除redis中的对应数据&#xff0c;直至下…

【java工具-灵活拉取数据库表结构和数据】

需求&#xff1a; 假设我们现在有一个需求&#xff0c;需要快速拉取数据库的某些表建表语句&#xff0c;和数据&#xff0c;平时做备份之类&#xff1b; 我这边自己写了个工具&#xff0c;不多废话&#xff0c;也不整虚的&#xff0c; 直接看代码&#xff1a; package com.…