【基础算法】单链表的OJ练习(3) # 移除链表元素 # 相交链表 #
前言
-
本章的
OJ
练习也是相对简单的,只要能够理解解题的思路,并且依照这个思路能够快速的写出代码,我相信,你的链表水平已经足够了。 -
对于
OJ
练习(2)
: ->传送门<-。其中两道题都可运用快慢指针的解题思路,这使得两个题都只需要遍历一次链表即可解答。 -
对于本章,是链表的
OJ
练习的最后一篇较为简单的章节,后续的OJ
练习将会上难度。
移除链表元素
-
题目链接:-> 传送门 <-。
-
该题目的描述为:给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。
-
这里我们采用的方法是在原链表的基础上重新连接节点,将 Node.val == val 的节点跳过不连接。
-
我们重新定义一个指向新连接的链表的头节点的指针
newhead
,然后在定义一个用来连接的指针cur
,最终连接好后返回newhead
即可。 -
将 Node.val != val 的节点作为新连接的链表的结点 ,如果一开始
head
为空或者head
链表里全是等于val
的结点,(初始化newnode = cur = NULL
)此时连接操作就不进行,后面返回newnode
(一直为NULL
)即可。
下面是代码实现:
struct ListNode* removeElements(struct ListNode* head, int val){
// cur为对新连接的链表的连接指针,newhead为新连接的链表的指向头节点的指针
struct ListNode* cur = NULL, * newhead = NULL;
struct ListNode* tmp = head;
while (tmp)
{
if (tmp->val != val) // 如果不等于val就连接
{
if (newhead == NULL) // 连接时如果新的头为空,就将该节点作为头节点
{
newhead = cur = tmp;
}
else // 正常连接
{
cur->next = tmp;
cur = cur->next;
}
}
tmp = tmp->next; // 到下一个节点判断
}
// 如果head为空或者head链表里面所有节点的val都为所给的val,就说明没有新的头,这里判断是为了防止空指针解引用
// 如果是正常情况,需要将新连接的最后一个节点的next指向NULL,如果已经指向NULL,多操作一步也没有问题
if (cur) cur->next = NULL;
// 最后返回新连接的链表的头
return newhead;
}
相交链表
-
题目链接:-> 传送门 <-。
-
该题目描述为:给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。
也就是:
解题思路一:【长链表先走长度差步】
- 分别遍历两个链表并求其长度,然后算出两个链表的长度差,让长的那个链表先走长度差步,再一起走,如果有相交节点,最终会同时到达相交的初始节点,返回该节点即可;如果没有相交,最后会同时到达
NULL
。
下面是代码实现:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int count1 = 0, count2 = 0;
struct ListNode *pa = headA, *pb = headB;
while (pa) pa = pa->next, count1 ++ ;
while (pb) pb = pb->next, count2 ++ ;
int max = count1, min = count2;
struct ListNode *maxList = headA, *minList = headB;
if (count1 < count2)
{
max = count2;
min = count1;
maxList = headB;
minList = headA;
}
int gap = max - min;
while (gap -- ) maxList = maxList->next;
while (maxList != minList)
{
maxList = maxList->next;
minList = minList->next;
}
return maxList;
}
解题思路二:【双指针直接遍历】
-
首先我们可以先判断这两个链表是否有一个为空或者都为空,有空的情况那么一定不相交,此时直接返回
NULL
。 -
如果两个链表相交,那么从相交的那个起始节点开始,后面的长度是相同的。由此我们定义两个指针
pa
与pb
分别指向headA
的头节点与headB
的头节点并同时向后遍历链表。 -
如果
pa
不为NULL
,则移到下一个节点,如果pb
不为空,也移到下一个节点。如果第一次遍历pa
为空,则将pa
指向headB
的头节点;如果第一次遍历pb
为空,则将pb
指向headA
的头节点。至于到底相不相交,第二遍遍历会见分晓。 -
我们假设两个链表相交,那么设从相交的初始节点开始到
NULL
的长度为n
,headA
的头节点到相交的初始节点的长度为x
,headB
的头节点到相交的初始节点的长度为y
。按照上一条的思路,当pa
第一次遍历到达NULL
时,pa
一共走了x + n
的长度,此时将pa
指向headB
的头节点;当pb
第一次遍历到达NULL
时,pb
一共走了y + n
的长度,此时将pb
指向headA
的头节点。仔细思考就会发现,pa
在headB
走到相交的初始节点还需走y
的长度,此时pa一共走了x + n + y
;pb
在headA
走到相交的初始节点还需走x
的长度,此时pb一共走了y + n + x
。这时,pa
走的长度与pb
走的长度恰好相等,且pa
与pb
都刚好指向相交的初始节点。所以,该方法能够有效的找出那个相交的初始节点。
- 如果两个链表不相交,也是一样,通过双指针分别依次向后遍历链表。如果两个链表长度相等,最终
pa
与pb
在第一次遍历的时候就都会到达NULL
,此时返回NULL
;如果两个链表长度不相等,同样的,在第一次遍历时,只要pa
或者pb
指向NULL
,就将pa
或者pb
指向另外一个链表的头节点,然后继续遍历。我们假设headA
链表的长度为x
,headB
链表的长度为y
,当pa
第一次遍历指向NULL
时,走的长度为x
,此时将pa
指向headB
的头节点;当pb
第一次遍历指向NULL
时,走的长度为y
,此时将pb
指向headA
的头节点。不出所料,两个指针在第二次遍历链表时最后同时指向NULL
,这是因为,pa
在headB
的遍历要走的长度为y
,此时pa
总共走的长度为x + y
;pb
在headA
的遍历要走的长度为x
,此时pb
总共走的长度为y + x
。可以看到,第二次遍历走完两个指针走的长度是相同的,并且两个指针都是指向NULL
。所以,两个链表不相交,遍历的两个指针最终都是同时指向NULL
。
下面是代码实现:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
// 如果其中有一个链表为空或者全为空,说明不可能相交,直接返回NULL
if(headA == NULL || headB == NULL) return NULL;
struct ListNode* pa = headA, * pb = headB;
// 对于headA与headB只有相交与不相交的情况
// 相交则跳出循环
// 不相交则再循环里面就返回
// pa == pb说明找到相交的初始节点了,条件判断为假,跳出循环
while (pa != pb)
{
// 同步向后遍历
pa = pa->next;
pb = pb->next;
// 如果两个指针都指向空,说明headA与headB不相交
if (pa == NULL && pb == NULL) return NULL;
// 如果pa遍历完headA就到headB继续遍历
if (pa == NULL) pa = headB;
// 如果pb遍历完headB就到headA继续遍历
if (pb == NULL) pb = headA;
}
// 这里返回pa或者pb都是可以的,都指向相交的那个初始节点
return pa;
}
写在最后
对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。
感谢阅读本小白的博客,错误的地方请严厉指出噢!
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击