LeetCode单链表OJ题目做题思路分享

news/2024/10/31 3:23:08/

目录

    • 移除链表元素
    • 链表的中间节点
    • 链表中倒数第K个节点
    • 合并两个有序链表

移除链表元素

链接: link
题目描述:
在这里插入图片描述
思路分享

我们上个博客分享了第一种方法,下面我们分析第二种方法:思路就是将每一个不等于我们要删除的值的节点依次尾插。
我们要记录我们尾插之后的新的头,以便于我们将新链表的头返回。
尾插的情况有以下两种:
如果当前要插入的值不是我们要删除的值时,我们要判断以下两种情况
1.链表没有元素,是空链表,这时就需要我们将链表新的头赋值为当前节点的值,并且此时的尾也指向链表新的头。newhead=tail=cur。
2.链表当中没有元素,不是空链表时,将此节点直接插入到当前链表的尾部。tail->next = cur,tail = tail ->next
如果当前要插入的值是我们要删除的值时:
新定义一个节点用来保存我们要删除的节点,将cur指针指向下一个节点,再free掉我们定义的节点。struct ListNode* del = cur;cur = cur->next ;free(del);
这里要注意两个点:
1.每次进行插入操作之后,cur指针都要向下移动
2.为了避免出现野指针问题,每次进行插入结束后,尾指针的next域都要置空。

这里出现一个问题,cur指针向下移动和tail的next域置空的顺序:
在这里插入图片描述
为什么第一个是正确的呢?
解答:
下图步骤意思是:让newhead和tail指针指向节点1
在这里插入图片描述
此时cur指向1节点,cur的next依旧指向的是节点2,这一点并没有改变,所以cur=cur->next指向的是节点2。
但是如果先将tail->next置空,那么cur->next也是空,因为此时cur和tail指向的是同一个节点的,所以此时cur->next也是NULL,会导致cur=cur->next时候找不到下一个节点,所以我们的顺序必须是先cur=cur->next,再将tail->next置空。
代码实现:

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;struct ListNode* tail = NULL;while (cur){if (cur->val != val)//和删除的值不相等{if (tail == NULL)//第一次插入{newhead = tail = cur;}else{tail->next = cur;tail = tail->next;}tail->next = NULL;cur = cur->next;}else//和删除的值相等{struct ListNode* del = cur;cur = cur->next;free(del);}}return newhead;
}

链表的中间节点

链接: link
题目描述:
在这里插入图片描述
题目思路:

快慢指针slow和fast
slow指针一次走一步,fast指针一次走两步。快指针速度是慢指针二倍,当快指针走到终点时,慢指针正好指向中间节点。
这里存在两种情况:刚好这两种情况可以作为我们循环的判断条件。
1.fast->next=NULL
在这里插入图片描述
2.fast=NULL
在这里插入图片描述

代码实现:

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

链表中倒数第K个节点

链接: link
题目描述:
在这里插入图片描述
题目思路:

本题我们的思路依然是一个快慢指针的问题
在这里插入图片描述

fast走到最后一个元素时,slow和fast同时向下一个节点移动,直到fast指向的位置为空,slow指向的位置就是我们要返回的元素。
本题我们要找倒数第1个节点,那么就以第一个节点为例,当slow和fast指针拉开1个举例时,两个指针同时向下移动,直到下面情况,slow指向的就是我们要找的值。
在这里插入图片描述
注意两点问题
1.如果链表的长度小于k的时候,也会造成fast空指针问题,所以在fast指针走k次的循环过程中,要保证不是因为单链表长度小于k而造成的空指针问题。
2.同时也要判断传过来的pListHead不为空或者k的值是否小于等于0,只要二者有一个满足,就要返回NULL。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{if (!pListHead || k <= 0)//保证传过来的头不是空并且k的值是有效值{return NULL;}//开始两个指针同时指向链表的头struct ListNode* slow = pListHead;struct ListNode* fast = pListHead;while (k--){if (fast){fast = fast->next;}else{return NULL;//单链表长度小于K会造成fast空指针}}while (fast){slow = slow->next;fast = fast->next;}return slow;
}

合并两个有序链表

链接: link
题目描述:
在这里插入图片描述
在这里插入图片描述
题目思路:

两个指针同时指向List1和List2两链表头部。开始进行链接:
本题需要5个指针,List1,List2,tail,newhead
1、如果List1的值比List2的值小,那么List1的头就是我们合并后链表新的头,newhead = List1,之后让List1指向下一个节点,并且tail指向刚刚被插入的节点。
与此同时如果List2的值比List1的值小,那么List2的头就是我们合并后链表新的头,newhead = List2,之后让List2指向下一个节点,并且tail指向刚刚被插入的节点。
2、有了新链表的头之后,剩下的步骤就是比较两个节点的大小,那个节点值大,就将哪个节点拿下来尾插,并且让尾指针tail指向该尾插的节点。
3、在进行不断的尾插的过程中肯定会有一条链表为空,如果是List1为空,那么直接让tail->next链接List2,否则链接List1。
注意:
我们还要注意一点就是,很有可能给我们的两条链表有一条是空链表,此时只需要返回那条不为空的链表就好。

代码实现:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}if(list1==NULL&&list2==NULL){return NULL;}struct ListNode* newhead = NULL;struct ListNode* tail = NULL;while(list1&&list2){if(list1->val<list2->val){if(newhead ==NULL){newhead = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{if(newhead ==NULL){newhead = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if(list1){tail->next = list1;}if(list2){tail->next = list2;}return newhead;
}

http://www.ppmy.cn/news/58647.html

相关文章

【JS笔记】JS操作字符串、对象、数组、时间对象、数值操作、定时器

这篇文章,主要介绍JS操作字符串、对象、数组、时间对象、数值操作、定时器。 目录 一、字符串 1.1、定义字符串 1.2、字符串方法 1.3、模板字符串 1.4、JSON字符串

UG NX二次开发(C++)-建模-修改NXObject或者Feature的颜色(一)

文章目录 1、前言2、在UG NX中修改Feature的颜色操作3、采用NXOpen(C)实现3.1 创建修改特征的方法3.2 调用ModifyFeatureColor方法3.3 测试结果 1、前言 在UG NX中&#xff0c;改变NXObject和Feature的操作是不相同的&#xff0c;所以其二次开发的代码也不一样&#xff0c;我们…

基于松鼠算法的极限学习机(ELM)回归预测-附代码

基于松鼠算法的极限学习机(ELM)回归预测 文章目录 基于松鼠算法的极限学习机(ELM)回归预测1.极限学习机原理概述2.ELM学习算法3.回归问题数据处理4.基于松鼠算法优化的ELM5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;本文利用松鼠算法对极限学习机进行优化&#xff0c;并…

unity NGUI使用方法

基本用法 很多基本模块比如按钮、slider等都能从Prefab中直接拖拽到场景中实现&#xff0c;但都需要有一个Collider&#xff08;Prefab已经自带&#xff09; 因为不仅是UI&#xff0c;所有带有Collider的游戏物体都能接收到OnClick&#xff0c; OnPress这样的事件——前提是需…

加强网络风险生命周期

当今业务环境中云原生应用程序的激增帮助组织简化了运营。 企业现在可以近乎实时地监控数据、与客户互动并分享见解&#xff0c;帮助他们克服曾经阻碍生产力的低效率问题。 然而&#xff0c;使用云也极大地扩展了企业可利用的攻击面。 CSPM、CWPP、CNAPP、SAST、SCA、IaC、D…

GO数组切片-线性数据结构

数据结构 类型 什么是类型 &#xff1f; 内存中的二进制数据本身没有什么区别&#xff0c;就是一串0或1的组合。 内存中有一个字节内容是0x63&#xff0c;他究竟是深恶 字符串?字符&#xff1f;还是整数&#xff1f; 本来0x63表示数字 但是文字必须编码成为0和1的组合 才能记…

Photoshop如何使用绘画和图像修饰之实例演示?

文章目录 0.引言1.给图像添加渐变色效果2.快速创建一副素描画3.清除图像中多余的景物4.快速融合两张图像5.调整图像光影6.人像面部瑕疵修除7.美化眼睛 0.引言 因科研等多场景需要进行绘图处理&#xff0c;笔者对PS进行了学习&#xff0c;本文通过《Photoshop2021入门教程》及其…

全面带你了解AIGC的风口

前言 一、AIGC的介绍 二、AIGC 的几个主要作用 三、实现AIGC过程的步骤 四、科技新赛道AIGC开始火了 五、AIGC对世界产生广泛的影响 六、AIGC技术的主要风口 &#x1f618;一、AIGC的介绍 AIGC (AI Generated Content) 是指通过人工智能技术生成的各种类型的内容&#xff0c;…