数据结构(01)——链表OJ

目录

移除链表元素

思路1

不创建虚拟头节点

思路2

创建虚拟头节点

反转链表

寻找链表中间节点

判断链表是否相交

回文链表

环形链表

环形链表||


移除链表元素

. - 力扣(LeetCode)

要想移除链表的元素,那么只需要将目标节点的前一个节点的next指针指向目标节点下一个节点的next指针

但是这里就会出现一个问题,如果头节点是目标值怎么办?

此时就有两种思路,一种就是分开讨论,当头节点为目标值时,头节点的next指针指向下一个节点,使下一个节点成为新的头节点

另一种就是创建虚拟头节点,这样在删除的时候就可以统一代码风格

思路1

不创建虚拟头节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    //头节点为目标值的情况
    while(head!=NULL&&head->val==val)
    {
        head = head->next;
    }
    //处理完头节点为目标值的情况
    ListNode* pcur = head;
    while(pcur!=NULL&&pcur->next!=NULL)
    {
        if(pcur->next->val==val)
        {
            pcur->next = pcur->next->next;
        }
        else
        {
            pcur = pcur->next;
        }
    }
    return head;
}

思路2

创建虚拟头节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    //使用虚拟头节点dummyhead来进行删除操作
    ListNode* dummyhead = (ListNode*)malloc(sizeof(ListNode));
    dummyhead->next = head;
    ListNode* pcur = dummyhead;
    while(pcur&&pcur->next)
    {
        if(pcur->next->val==val)
        {
            pcur->next = pcur->next->next;
        }
        else
        {
            pcur = pcur->next;
        }
    }
    return dummyhead->next;
}

反转链表

206. 反转链表 - 力扣(LeetCode)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) 
{
    ListNode* cur = head;
    ListNode* prev = NULL;
    ListNode* tmp = NULL;
    while(cur)
    {
        tmp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = tmp;
    }
    return prev;
}

让我们画一个图来解释这个代码

 

当我们遍历完这个链表之后,返回的prev就会依次从后往前返回链表中的元素了 

寻找链表中间节点

这道题的思路是双指针法,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到链表结尾时,慢指针的位置就是链表的中间节点

876. 链表的中间结点 - 力扣(LeetCode)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

判断链表是否相交

如果要判断链表是否相交,那么就要分别遍历这两个链表,判断他们的尾节点的地址是否相同,其次再找到相交的位置的元素

. - 力扣(LeetCode)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    int lenA = 1;
    int lenB = 1;
    ListNode* curA = headA;
    ListNode* curB = headB;
    while(curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB = curB->next;
        lenB++;
    }
    //判断地址是否相等
    if(curA!=curB)
    {
        return NULL;
    }
    //使用假设法
    int gap = abs(lenA-lenB);
    ListNode* longlist = headA;
    ListNode* shortlist = headB;
    if(lenB>lenA)
    {
        longlist = headB;
        shortlist = headA;
    }
    //先让长指针走到短指针的位置,然后开始地址比较
    while(gap--)
    {
        longlist = longlist->next;
    }
    while(shortlist!=longlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return shortlist;
}

回文链表

回文链表的思路是先找到链表的中间节点,然后将中间节点后面的元素反转,再和前面的元素一个一个比较,如果都i相等,那么就是回文链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;

bool isPalindrome(struct ListNode* head)
{
    //先找到链表的中间元素
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    //反转中间节点之后的元素
    ListNode* cur = slow;
    ListNode* prev = NULL;
    ListNode* tmp = NULL;
    while(cur)
    {
        tmp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = tmp;
    }
    while(head&&prev)
    {
        if(head->val!=prev->val)
        {
            return false;
        }
        
        prev = prev->next;
        head = head->next;
    }
    return true;
}

环形链表

. - 力扣(LeetCode)

判断是否为环形链表,依然是快慢指针的方法,非常简单,直接上代码了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow==fast)
    {
        return true;
    }
    }
    return false;
}

环形链表||

环形链表||

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //判断是否有环
        if(slow==fast)
        {
            ListNode* meet = head;
            while(meet!=slow)
            {
                slow = slow->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

环形链表||

在这个代码中,我们将meet从head开始遍历,那么当meet和slow相遇的节点就是环形链表的入口处

那么我们如何证明呢?

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

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

相关文章

07_for循环返回值while循环

文章目录 1.循环返回值2.yield接收for返回值3.scala调用yield方法创建线程对象4.scala中的while循环5.scala中的流程控制 1.循环返回值 for循环返回值是Unit 原因是防止产生歧义; 2.yield接收for返回值 // 2.yield关键字打破循环,可以使for循环输出…

智慧农业设备——虫情监测系统

随着科技的不断进步和农业生产的日益现代化,智慧农业成为了新时代农业发展的重要方向。其中,虫情监测系统作为智慧农业的重要组成部分,正逐渐受到广大农户和农业专家的关注。 虫情监测系统是一种基于现代传感技术、图像识别技术和大数据分析技…

面试笔记——线程池

线程池的核心参数&#xff08;原理&#xff09; public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler)corePoolSize …

25计算机考研院校数据分析 | 四川大学

四川大学(Sichuan University)简称“川大”&#xff0c;由中华人民共和国教育部直属&#xff0c;中央直管副部级建制&#xff0c;是世界一流大学建设高校、985工程”、"211工程"重点建设的高水平综合性全国重点大学&#xff0c;入选”2011计划"、"珠峰计划…

PostgreSQL的学习心得和知识总结(一百四十)|深入理解PostgreSQL数据库 psql工具 \set 变量内部及HOOK机制

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《PostgreSQL数据库内核分析》 2、参考书籍&#xff1a;《数据库事务处理的艺术&#xff1a;事务管理与并发控制》 3、PostgreSQL数据库仓库…

【能力展现】魔改ZXING源码实现商业级DM码检测能力

学习《OpenCV应用开发&#xff1a;入门、进阶与工程化实践》一书 做真正的OpenCV开发者&#xff0c;从入门到入职&#xff0c;一步到位&#xff01; 什么是DM码 dataMatrix是一种二维码&#xff0c;原名datacode&#xff0c;由美国国际资料公司于1989年发明。dataMatrix二维码…

GuildFi升级为Zentry的背后 链游公会的探索与转型

​链游即区块链游戏&#xff0c;指依托区块链技术构建的游戏产品。其与传统游戏的最大区别在于区块链的去中心化特性对玩家的资产有着天然的确权行为&#xff0c;因此玩家在链游中的资产是作为玩家的个人资产存在。较于 GameFi 来说&#xff0c;链游的包含范围更大&#xff0c;…

吴恩达机器学习笔记:第 8 周-14降维(Dimensionality Reduction) 14.3-14.5

目录 第 8 周 14、 降维(Dimensionality Reduction)14.3 主成分分析问题14.4 主成分分析算法14.5 选择主成分的数量 第 8 周 14、 降维(Dimensionality Reduction) 14.3 主成分分析问题 主成分分析(PCA)是最常见的降维算法。 在 PCA 中&#xff0c;我们要做的是找到一个方向…

【高校科研前沿】华东师大白开旭教授博士研究生李珂为一作在RSE发表团队最新成果:基于波谱特征优化的全球大气甲烷智能反演技术

文章简介 论文名称&#xff1a;Developing unbiased estimation of atmospheric methane via machine learning and multiobjective programming based on TROPOMI and GOSAT data&#xff08;基于TROPOMI和GOSAT数据&#xff0c;通过机器学习和多目标规划实现大气甲烷的无偏估…

OS复习笔记ch5-1

引言 讲解完进程和线程之后&#xff0c;我们就要来到进程的并发控制这里&#xff0c;这一章和下一章是考试喜欢考察的点&#xff0c;有可能会出大题&#xff0c;面试也有可能会被频繁问到&#xff0c;所以章节内容较多。请小伙伴们慢慢食用&#xff0c;看完之后多思考加强消化…

【JPE】顶刊测算-工业智能化数据(附stata代码)

数据来源&#xff1a;国家TJ局、CEC2008、IFR数据 时间跨度&#xff1a;2006-2019年 数据范围&#xff1a;各省、地级市 数据指标&#xff1a; 本数据集展示了2006-2019年各省、各地级市的共工业智能化水平的数据。本数据集包含三种构建工业机器人密度来反映工业智能化水平的方…

基于Springboot的数字化农家乐管理平台(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的数字化农家乐管理平台&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系…

Apache Seata基于改良版雪花算法的分布式UUID生成器分析2

title: 关于新版雪花算法的答疑 author: selfishlover keywords: [Seata, snowflake, UUID, page split] date: 2021/06/21 本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 关于新版雪花算法的答疑 在上一篇关于新版雪花算法的解析中…

web前端学习笔记4

4. 盒子模型 4.0 代码地址 https://gitee.com/qiangge95243611/java118/tree/master/web/day044.1 什么是盒子模型(Box Model) 所有HTML元素可以看作盒子,在CSS中,"box model"这一术语是用来设计和布局时使用。 CSS盒模型本质上是一个盒子,封装周围的HTML元素,…

在Docker中部署Java应用:Java版本隔离的实践案例

在Docker中部署Java应用&#xff1a;Java版本隔离的实践案例 人生就是一场又一场的相遇&#xff0c;一个明媚&#xff0c;一个忧伤&#xff0c;一个华丽&#xff0c;一个冒险&#xff0c;一个倔强&#xff0c;一个柔软&#xff0c;最后那个正在成长。 背景需求 在软件开发和部…

Debian 12 -bash: netstat: command not found 解决办法

问题表现&#xff1a; debian 12系统中&#xff0c;不能使用 netstat命令 处理办法&#xff1a; netstat 命令就的net-tools中&#xff0c;把net-tools工具安装上就好了。 apt-get install netstat 安装之后就可以使用netstat 命令了&#xff0c;如查询端口情况&#xff1a; …

基于SpringBoot+Vue高校宣讲会管理系统设计与实现

项目介绍&#xff1a; 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装高校宣讲会管理系统软件来发挥其高效地信息…

C# Web控件与数据感应之 Control 类

目录 关于数据感应 Control 类 范例运行环境 simpleDataListEx方法 设计 实现 调用示例 数据源 调用 小结 关于数据感应 数据感应也即数据捆绑&#xff0c;是一种动态的&#xff0c;Web控件与数据源之间的交互&#xff0c;诸如 ListControl 类类型控件&#xff0c;在…

pytest教程-35-钩子函数-pytest_unconfigure

领取资料&#xff0c;咨询答疑&#xff0c;请➕wei: June__Go 上一小节我们学习了pytest_configure钩子函数的使用方法&#xff0c;本小节我们讲解一下pytest_unconfigure钩子函数的使用方法。 pytest_unconfigure(config) 是一个 pytest 钩子函数&#xff0c;它在 pytest 退…

【linux运维】vim基础应用

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了学习基本的shell编程和linux命令&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于b站大学——linux运维课程进行的&#xff0c;…