关于链表节点的定义:
1 | struct Node { |
1. 删除链表节点
题目描述:给定链表的头指针和一个节点指针,在O(1)时间删除该节点。
分析:主要思想是用下一个节点数据覆盖要删除的节点,然后再删除下一个节点。但是如果要删除的节点是尾节点时,就行不通了。
代码如下:
1 | //O(1)时间删除链表节点,从无头单链表中删除节点 |
2. 单链表反转
题目描述:输入一个单向链表,输出逆序反转后的链表
分析:链表的转置是一个很常见,很基础的数据结构问题,非递归的算法很简单,用三个临时指针pre
、head
、next
在链表上循环一遍即可。递归算法也比较简单,具体如下
1 | // 单链表反转,非递归方法 |
1 | // 单链表反转,递归方法 |
3. 求链表倒数第k个节点
题目描述:输入一个单项链表,输出该链表中倒数第k个节点,链表倒数第0个节点为链表的尾节点。
分析:设置两个指针p1
、 p2
,首先p1
和 p2
都指向head,然后p2
向前走k步,这样p1
和 p2
之间就间隔了k个节点,然后p1
和 p2
同时向前移动,直至p2走到链表末尾。
1 | // 倒数第k个节点 |
4. 求链表的中间节点
题目描述:求链表的中间节点,如果链表的长度为偶数,返回中间两个节点的任意一个,若为奇数,则返回中间节点
分析:首先想到的是,先计算出链表的长度,然后计算出中间节点所在链表顺序的位置。但是还有一种更搞笑的思路,只需要扫描一遍链表。通过两个指针p1
和 p2
,同时从链表头节点开始,p1
每次移动两步, p2
每次移动一步,当p1
移动到链表尾节点的时候,p2
所在的位置就是链表的中间节点
1 | // 求链表的中间节点 |
5. 判断单链表是否存在环
题目描述:输入一个单向链表,判断该链表是否存在环
分析:也是通过两个指针,分别从链表的头节点开始出发,一个每次向后移动一步,另一个移动两步,两个指针的移动速度不一样,如果存在环,那么两个指针一定会在环里相遇。
1 | // 判断单链表是否存在环,参数circleNode是环内节点 |
6. 找到环的入口点
题目描述:输入一个单向链表,判断链表是否有环。如果链表存在环,如何找到环的入口点
分析:由上题可知,按照 p2
每次两步,p1
每次一步的方式走,发现 p2
和 p1
重合,确定了单向链表有环路了。接下来,让p2
回到链表的头部,重新走,每次步长不是走2了,而是走1,那么当 p1 和 p2 再次相遇的时候,就是环路的入口了。
为什么?:假定起点到环入口点的距离为 a,p1
和 p2
的相交点M与环入口点的距离为b,环路的周长为L,当 p1
和 p2
第一次相遇的时候,假定 p1
走了 n 步。那么有:
p1
走的路径: a+b = n
;
p2
走的路径: a+b+k*L = 2*n
; p2
比 p1
多走了k圈环路,总路程是p1
的2倍
根据上述公式可以得到 k*L=a+b=n
。显然,如果从相遇点M开始,p1
再走 n 步的话,还可以再回到相遇点,同时p2
从头开始走的话,经过n步,也会达到相遇点M。
显然在这个步骤当中 p1
和 p2
只有前 a 步走的路径不同,所以当 p1
和 p2
再次重合的时候,必然是在链表的环路入口点上。
1 | //找到环的入口点 |
7. 判断两个链表是否相交
题目描述:给出两个单向链表的头指针,比如h1、h2,判断这两个链表是否相交。这里为了简化问题,我们假设两个链表均不带环。
分析:
直接循环判断第一个链表的每个节点是否存在第二个链表中。很显然 ,不够效率。
针对第一个链表直接构造hash表,然后查询hash表,判断第二个链表的每个节点是否在hash表出现,如果所有的第二个链表的节点都能在hash表中找到,即说明第二个链表与第一个链表有相同的节点。时间复杂度为为线性:O(Length(h1) + Length(h2)),同时为了存储第一个链表的所有节点,空间复杂度为O(Length(h1))。是否还有更好的方法呢,既能够以线性时间复杂度解决问题,又能减少存储空间?
转换为环的问题。把第二个链表接在第一个链表后面,如果得到的链表有环,则说明两个链表相交。如何判断有环的问题上面已经讨论过了,但这里有更简单的方法。因为如果有环,则第二个链表的表头一定也在环上,即第二个链表会构成一个循环链表,我们只需要遍历第二个链表,看是否会回到起始点就可以判断出来。这个方法的时间复杂度是线性的,空间是常熟。
进一步考虑“如果两个没有环的链表相交于某一节点,那么在这个节点之后的所有节点都是两个链表共有的”这个特点,我们可以知道,如果它们相交,则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点,所以这成了我们简化解法的一个主要突破口。那么,我们只要判断两个链表的尾指针是否相等。相等,则链表相交;否则,链表不相交。
所以,先遍历第一个链表,记住最后一个节点。然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则,不相交。这样我们就得到了一个时间复杂度,它为O((Length(h1) + Length(h2)),而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N),空间复杂度为O(1),显然比解法三更胜一筹。
解法四的代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//判断两个链表是否相交
bool isIntersect(Node *h1,Node *h2) {
//异常判断
if(h1 == NULL || h2 == NULL) return false;
while(h1->next != NULL) {
h1 = h1->next;
}
while(h2->next != NULL) {
h2 = h2->next;
}
//尾节点是否相同
if(h1 == h2) return true;
return false;
}
8. 链表🈶环,如何判断相交
题目描述:上面的问题都是针对链表无环的,那么如果现在,链表是有环的呢?上面的方法还同样有效么?
分析:如果有环且两个链表相交,则两个链表都有共同一个环,即环上的任意一个节点都存在于两个链表上。因此,就可以判断一链表上俩指针相遇的那个节点,在不在另一条链表上。
1 | //判断两个带环链表是否相交 |
9. 两链表相交的第一个公共节点
题目描述:如果两个无环单链表相交,怎么求出他们相交的第一个节点呢?
分析:采用对齐的思想。计算两个链表的长度 L1 , L2,分别用两个指针 p1
, p2
指向两个链表的头,然后将较长链表的 p1
(假设为 p1
)向后移动L2 - L1
个节点,然后再同时向后移动p1
, p2
,直到 p1 = p2
。相遇的点就是相交的第一个节点。
1 | //求两链表相交的第一个公共节点 |