相交链表（LeetCode 160）
文章目录
- 1.问题描述
- 2.难度等级
- 3.热门指数
- 4.解题思路
- 方法一：暴力法
- 方法二：哈希表
- 方法三：双栈
- 方法四：双指针：记录链表长度
- 方法五：双指针：互换遍历
- 5.实现示例
- 参考文献
1.问题描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
示例 1：
相交返回结点 8。
示例 2：
相交返回结点 2。
示例 3：
不相交返回 null。
进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
2.难度等级
Easy。
3.热门指数
★★★★★
出题公司：阿里、腾讯、字节。
4.解题思路
解这道题之前，我们需要首先明确一个概念：何为相交？
相交指的是结点为同一个结点，那么指向结点的指针是相同的，而不是第一个结点值相同。
如果不考虑时间和空间复杂度，那么有多种解法。
假设 m 和 n 是分别是链表 headA 和 headB 的长度。
方法一：暴力法
从头开始遍历第一个链表，遍历第一个链表的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点。
若第一个链表遍历结束后，还未找到相同的节点，即不存在交点。
时间复杂度：
。
空间复杂度：
。
方法二：哈希表
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，将链表中的每个节点加入哈希表中。然后遍历链表 headB，判断节点是否在哈希表中。
如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
时间复杂度： O(m+n)，需要遍历两个链表各一次。
空间复杂度： O(m)，需要使用哈希表存储链表 headA 的全部节点。
方法三：双栈
我们可以从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点。每遍历到一个节点时，就将该节点入栈。两个链表都入栈结束后。
则通过判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道，若两个链表相交，则从第一个相交节点开始，后面的节点都相交。
若两链表相交，则循环出栈，直到遇到两个出栈的节点不相同，则这个节点的后一个节点就是第一个相交的节点。
时间复杂度： O(m+n)。需要遍历两个链表各两次，一次是入栈，一次是出栈。
空间复杂度： O(m+n)，需要使用两个栈存储链表 headA 和 headB 的所有结点。
方法四：双指针：记录链表长度
同时遍历两个链表到尾部，同时记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。
有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为 len1，短的链表长度为 len2。
则先让较长的链表向后移动 len1-len2 个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。
时间复杂度：
，两个指针同时遍历两个链表，然后再遍历两个链表至相同结点。
空间复杂度：
。
方法五：双指针：互换遍历
当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：
- 每步操作需要同时更新指针 pA 和 pB。
- 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
- 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
- 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
为什么第一次遍历完后互换从头遍历后，如果相交会同时到达相交结点呢？
假设下面是一个相交的两个链表，省去了结点。其中链表 headA 的长度为 a + c = m，链表 headB 的长度为 b + c = n。
因为 a + c + b 等于 b + c + a，所以第一次遍历完后互换从头遍历，会同时到达相交结点。
如果两个链表不相交，也会同时到达尾结点，因为 m + n 等于 n + m。
时间复杂度：
，两个指针同时遍历两个链表，然后再遍历两个链表至相同结点。
空间复杂度：
。
5.实现示例
面以 Golang 为例，给出「双指针：互换遍历」的实现。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
pA, pB := headA, headB
for pA != nil || pB != nil {
if pA == pB {
return pA
}
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
return nil
}