关于环的问题,
介绍几个个经典的题目:
1.求链表倒数第k个结点
最经典,最常见的解法就是,设置两个指针p1,p2,一开始分别指向头结点,首先p2先移动k个节点,之后开始p1,p2每次移动1个节点,直到p2达到最后一个节点位置,那么p1指向的就是倒数第k个节点。
不过这种解法主要是针对单链表,且链表中不存在环的,如果是双向链表,或者是存在环的链表呢?
在判断是否在最后一个节点上就会出现问题了,ps.循环链表中判断最后一个节点就需要查看其pre指针指向的节点是否是刚才遍历过的节点。对于存在环的节点判断最后一个节点就有点麻烦了:
判断一个链表是否存在环
环的定义如上:
定义两个指针,开始的时候分别指向head,之后p1每次移动一个节点,p2每次移动两个节点,如果p2遇到null 的时候,不存在换否在p1,p2肯定在环内相遇。当p1==p2的时候,退出,存在环
判断两个链表是否相交
对于这个问题,这里的相交不会存在“X”的相交,而是“Y”形状的相交。
解法一
使用两个for循环来同时遍历两个数组,来发现首个相同的节点,不过时间复杂度会达到O(M*N)
解法二
使用hash表存储第一个链表的所有元素,通过遍历第二个链表,检查是否相同的节点在hash表中,有的话则说明两个链表有相同的子序列,否则就没有。时间复杂度为O(M+N),空间复杂度为O(M),不是很理想
解法三
如果链表相交则链表的最后一个节点一定是相同的,我们只需要判断最后一个节点是否相同即可。时间复杂度为O(M+N),空间复杂度减少到O(1)
当然上述几种方法都是建立在无环链表的基础之上的。
所以总结如下解决办法:
1.先判断带不带环
2.如果都不带环,就判断尾节点是否相等
3.如果都带环,判断第一个链表上是否存在环时---俩指针相遇(在环中相遇)的那个节点,在不在另一条链表上。如果在,则相交,如果不在,则不相交。
判断一个存在环的链表的环的第一个节点
在网上看到一个解决办法,类似龟兔赛跑的原理,定义两个指针p1,p2。p2一直向前走,p1,也是向前走,每走一步检查下是否赶上p2,如果赶上了,就从头再跑,此时p2向前走一步,如果没赶上,则继续往前走,此时p2停下等待,如此循环,直到,p1==p2->next,此时p2计时所求的点。
求两个相交链表的首个交点
解法1:
使用两个for循环来同时遍历两个数组,来发现首个相同的节点,不过时间复杂度会达到O(M*N)
解法2
每个节点添加一个vist访问标志位,来表示已经访问过的节点。首先遍历第一个链表,将访问位置true,然后遍历第二个链表,当发现vist的位true时,则这个节点就是两个链表相交的首个交点。时间复杂度为O(M+N)
解法3:
首先求出两个链表的长度c,d;
求出f=abs(c-d);
较长的那个链表首先遍历f个长度,然后两个链表同时开始向下遍历,并进行比较,第一个相等的即为两个链表相交的首个交点。
- 大小: 1.6 KB
分享到:
相关推荐
C语言双向链表 -------------------------------------------精品
链表构造
用c语言描述的线形表---链表---带头节点单链表的就地逆置
链表排序--选择排序.cpp
双链表-循环链表-静态链表.pdf
java数组和链表底层-链表的底层原理和实现 数组和链表.pdf
Java数组链表效率-Java数组和链表三种遍历效率对比 数组和链表.pdf
链表创建-输出-删除-示例2.cpp
包含各种类型的链表,例如简单链表、带头结点的链表、双向链表、合并链表、递归链表等。
剑指offer计划2(链表)---java(csdn)————程序
链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序链表逆序
c语言数组与链表转化-分别用数组和链表实现堆栈(C语言版)(转) 数组和链表.pdf
利用链表的基本操作来实现多项式的乘法 用c语言编写
练习 : 使用内核链表建一个简单的学生管理系统,并把信息存于文件中
c语言-学生成绩管理系统-链表实现-源码
二叉树-二叉链表结构-构造和输出.cpp
说明:字符串的比较和拷贝可以使用标准库函数strcmp和strcpy,使用方法如下: strcmp(name,"#####")!=0 //比较name中存放的字符串是不是"#####" strcpy(ptr->name,name) //将name数组中的字符串复制到ptr指向结点的...
c语言链表数组-c语言手写单链表实现,数组和链表结构对比小结和个人理解 数组和链表.pdf
链表实现同时包括单链表逆序实现、求单链表倒数第N个数、用标尺法找单链表中间节点
哈希表--链表 哈希表--链表 哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表