Leetcode——面试题02.04.分割链表

面试题 02.04. 分割链表 - 力扣(LeetCode) 

对于该链表OJ,我们两种大的方向:

1.在原链表上修改;2.创建新链表,遍历原链表。

在原链上进行修改:如果该节点的val小于x则继续往后走,如果大于等于x则将该节点尾插到该链表,然后删除该节点,继续遍历;

创建新链表,遍历原链表:对于这种方式也有两种

  • 创建一个新链表,遍历原链表,如果节点的val小于x则头插到新链表中,如果大于等于x则尾插到新链表中。
  • 创建两个新链表:little和big。遍历原链表,如果节点的val值小于x则尾插到little链表中,如果节点的val值大于等于x则尾插到big链表中,遍历完后,连接这两个新链表即可。

我们今天来实现创建两个新链表的方式来解决问题。

我们在创建链表的时候可以采取带头链表的方式,这样可以避免重复代码的出现。 

新链表前的红色圆点就代表着头节点也叫做哨兵位。 我们创建完链表并遍历完之后,就得到了两个大小链表,我们只需要将这两个连接起来就可以了。

我们通过上面代码连接好之后 ,就得到了如图的链表,那么是否可以直接返回little->next?

答案是不行!!! 在该链表中出现了循环结构,程序会陷入死循环。那么怎么解决这个问题呢?

该问题出现的原因是因为big链表的尾节点的next指针指向的不是NULL造成的。我们只需要在连接之前将big链表的尾节点的next指针指向NULL就行了。

 下面附上完整代码(注:该代码是leetcode的解题代码,不包括main函数)

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
    //已知链表为空,直接返回NULL
    if(head == NULL)
    {
        return NULL;
    }
    //已知链表不为空
    //创建两个新链表,为了避免重复代码,可以利用哨兵位
    ListNode* little = (ListNode*)malloc(sizeof(ListNode));
    ListNode* littletail = little;
    ListNode* big = (ListNode*)malloc(sizeof(ListNode));
    ListNode* bigtail = big;
    //遍历原链表
    while(head)
    {
        if(head->val<x)
        {
            //小于x,将节点尾插little中
            littletail->next = head;
            littletail = littletail->next;
        }
        else
        {
            //大于等于x,将该节点尾插到big中
            bigtail->next = head;
            bigtail = bigtail->next;
        }
        //遍历下一个节点
        head = head->next;
    }
    //退出循环说明已经遍历完了原链表
    //修改bigtail指向,否则会陷入死循环
    bigtail->next = NULL;

    //连接大小链表
    //因为这两个链表都是带头链表,所以连接时要指向头结点的下一个节点
    littletail->next = big->next;
    
    return little->next;
}

完!

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

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

相关文章

用于复杂任务的 AI 编码引擎:多文件多步骤拆解实现 | 开源日报 No.239

plandex-ai/plandex Stars: 3.1k License: AGPL-3.0 plandex 是一个用于复杂任务的 AI 编码引擎。 使用长时间运行的代理完成跨多个文件且需要多个步骤的任务将大型任务分解为较小子任务&#xff0c;逐一实现&#xff0c;直至完成整个工作帮助处理积压工作、使用陌生技术、摆…

如何在Spring Boot中配置数据库密码加密

如何在Spring Boot中配置数据库密码加密&#xff1f; alibaba/druid Wiki GitHub 使用ConfigFilter alibaba/druid Wiki GitHub 巧用Druid数据源实现数据库连接密码的加密解密功能 import com.alibaba.druid.filter.config.ConfigTools;public class Testttt {public stat…

后端方案设计文档结构模板可参考

文章目录 1 方案设计文档整体结构2 方案详细设计2.1 概要设计2.2 详细设计方案2.2.1 需求分析2.2.2 业务流程设计2.2.3 抽象类&#xff1a;实体对象建模2.2.4 接口设计2.2.5 存储设计 1 方案设计文档整体结构 一&#xff0c;现状&#xff1a;把项目的基本情况和背景都说清楚&a…

Grafana 添加一台管理服务器

1、修改prometheus.yml 添加新服务器信息 2、重启pro 3、导入node文件 4、启动node 5、检验数据

Vue3(管理系统)-封装axios(utils)

一、在utils下编写request.js实例 1.添加基地址&#xff0c;设置超时时间 import axios from axios const baseURL http://big-event-vue-api-t.itheima.net const instance axios.create({// TODO 1. 基础地址&#xff0c;超时时间baseURL,timeout: 3000 }) 2.添加请求拦截…

在Ubuntu linux操作系统上操作MySQL数据库常用的命令

检查是否安装了MySQL&#xff0c;或检查MySQL的状态&#xff1a; sudo systemctl status mysql或 sudo systemctl status mysql.service如果mysql有安装&#xff0c;上面这条命令会返回mysql的状态active或inactive。 卸载mysql数据库 第一步是停了数据库&#xff1a; sud…

【SQL Server】入门教程-基础篇(三)

目录 前言 SQL 常用函数学习 AVG – 平均值 COUNT – 汇总函数 ​编辑MAX – 最大值 ​编辑MIN – 最小值 ​编辑SUM – 求和 UCASE/UPPER – 大写 LCASE/LOWER – 小写 ROUND – 数值取舍 NOW/SYSDATE – 当前时间 前言 这一篇博客&#xff0c;是Sql Server函数学…

Spring MVC入门程序

SpringMVC入门程序 一、实现思路 掌握Spring MVC入门程序&#xff0c;能够实现入门程序的编写 二、编码实现 1、新建项目 项目&#xff1a;maven&#xff0c;原型&#xff1a;maven-archetype-webapp&#xff0c;GroupID&#xff1a;com.sw 引入pom依赖 2、补充项目目录 src…

# 从浅入深 学习 SpringCloud 微服务架构(七)Hystrix(3)

从浅入深 学习 SpringCloud 微服务架构&#xff08;七&#xff09;Hystrix&#xff08;3&#xff09; 一、hystrix&#xff1a;通过 Actuator 获取 hystrix 的监控数据 1、Hystrix 的监控平台介绍&#xff1a; 1&#xff09;Hystrix 除了实现容错功能&#xff0c;Hystrix 还…

vue3中使用crypto-js库进行加密/解密

使用crypto-js库进行加密/解密 安装 npm install crypto-js 基本使用 <template><div>使用crypto-js库进行加密/解密</div> </template><script setup> import CryptoJS from crypto-js; import { onMounted } from vue;// 加密函数 const encr…

监视器和显示器的区别,普通硬盘和监控硬盘的区别

监视器与显示器的区别&#xff0c;你真的知道吗&#xff1f; 中小型视频监控系统中&#xff0c;显示系统是最能展现效果的一个重要环节&#xff0c;显示系统的优劣将直接影响视频监控系统的用户体验满意度。 中小型视频监控系统中&#xff0c;显示系统是最能展现效果的一个重要…

UDP!!!

UDP!!! 一 : 传输层的协议:二 : UDP2.1 UDP长度2.2 UDP校验和2.2.1 : 为什么会出现传输出错的情况??2.2.3: 对数据进行校验的方式CRCmd5 三 : UDP的适用场景 一 : 传输层的协议: 传输层的协议有UDP,TCP UDP:无连接,不可靠传输,面向数据报,全双工 TCP:有连接,可靠传输,面向字…

深度学习之基于YOLOv5烟花燃放智能检测系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景与意义 在庆祝和特殊节日中&#xff0c;烟花燃放作为传统的庆祝方式之一&#xff0c;深受人们的喜爱。…

ChatGPT的AI“记忆”可以记住付费客户的偏好

通过记住有关 ChatGPT Plus 订阅者的详细信息&#xff0c;OpenAI 的聊天机器人添加了更多个人助理风格的功能 OpenAI 在今年二月宣布了 “记忆 ”功能&#xff0c;该功能允许 ChatGPT 更永久地存储查询、提示和其他自定义功能。当时&#xff0c;只有 “一小部分 ”用户可以使用…

ChatGPT 网络安全秘籍(一)

原文&#xff1a;zh.annas-archive.org/md5/6b2705e0d6d24d8c113752f67b42d7d8 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 前言 在不断发展的网络安全领域中&#xff0c;由 OpenAI 推出的 ChatGPT 所代表的生成式人工智能和大型语言模型&#xff08;LLMs&#xf…

Mybatis.net + Mysql

项目文件结构 NuGet下载Mybatis.net相关包&#xff1a;IBatisNet 安装完成后&#xff0c;会显示在&#xff0c;在已安装页面。同时&#xff0c;在管理器中的引用列表中&#xff0c;会多出来两个引用文件 IBatisNet.CommonIBatisNet.DataMapper 安装 Mysql.data。 注意&#xff…

深入理解正则表达式:从入门到精通

title: 深入理解正则表达式&#xff1a;从入门到精通 date: 2024/4/30 18:37:21 updated: 2024/4/30 18:37:21 tags: 正则Python文本分析日志挖掘数据清洗模式匹配工具推荐 第一章&#xff1a;正则表达式入门 介绍正则表达式的基本概念和语法 正则表达式是一种用于描述字符串…

Android 音视频播放器 Demo(二)—— 音频解码与音视频同步

音视频编解码系列目录&#xff1a; Android 音视频基础知识 Android 音视频播放器 Demo&#xff08;一&#xff09;—— 视频解码与渲染 Android 音视频播放器 Demo&#xff08;二&#xff09;—— 音频解码与音视频同步 RTMP 直播推流 Demo&#xff08;一&#xff09;—— 项目…

使 Elasticsearch 和 Lucene 成为最佳向量数据库:速度提高 8 倍,效率提高 32 倍

作者&#xff1a;来自 Elastic Mayya Sharipova, Benjamin Trent, Jim Ferenczi Elasticsearch 和 Lucene 成绩单&#xff1a;值得注意的速度和效率投资 我们 Elastic 的使命是将 Apache Lucene 打造成最佳的向量数据库&#xff0c;并继续提升 Elasticsearch 作为搜索和 RAG&a…

Jenkins自动化搭建记录

每一份努力都是有一份期盼&#xff0c;每一份付出都是为了有更多的收获。 本文记录一次搭建Jenkins自动参数化打包APK的实现过程和碰到的问题&#xff0c;实现了在Windows和Mac系统下的自动化打包流程。 因为Jenkins的安装过程在网上的教程很多&#xff0c;这里就不在赘述。 …