相交链表（LeetCode 160）

1.问题描述

给两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果不存在相交节点，返回 null 。

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

示例 1：

相交返回结点 8。

示例 2：

相交返回结点 2。

示例 3：

不相交返回 null。

进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

2.难度等级

Easy。

3.热门指数

★★★★★

出题公司：阿里、腾讯、字节。

4.解题思路

解这道题之前，我们需要首先明确一个概念：何为相交？

相交指的是结点为同一个结点，那么指向结点的指针是相同的，而不是第一个结点值相同。

如果不考虑时间和空间复杂度，那么有多种解法。

假设 m 和 n 是分别是链表 headA 和 headB 的长度。

方法一：暴力法

从头开始遍历第一个链表，遍历第一个链表的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点。

若第一个链表遍历结束后，还未找到相同的节点，即不存在交点。

时间复杂度： $O(n^2)$。

空间复杂度： $O(1)$。

方法二：哈希表

判断两个链表是否相交，可以使用哈希集合存储链表节点。

首先遍历链表 headA，将链表中的每个节点加入哈希表中。然后遍历链表 headB，判断节点是否在哈希表中。

如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。

时间复杂度： O(m+n)，需要遍历两个链表各一次。

空间复杂度： O(m)，需要使用哈希表存储链表 headA 的全部节点。

方法三：双栈

我们可以从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点。每遍历到一个节点时，就将该节点入栈。两个链表都入栈结束后。

则通过判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道，若两个链表相交，则从第一个相交节点开始，后面的节点都相交。

若两链表相交，则循环出栈，直到遇到两个出栈的节点不相同，则这个节点的后一个节点就是第一个相交的节点。

时间复杂度： O(m+n)。需要遍历两个链表各两次，一次是入栈，一次是出栈。

空间复杂度： O(m+n)，需要使用两个栈存储链表 headA 和 headB 的所有结点。

方法四：双指针：记录链表长度

同时遍历两个链表到尾部，同时记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。

有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为 len1，短的链表长度为 len2。

则先让较长的链表向后移动 len1-len2 个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。

时间复杂度： $O(m+n)$，两个指针同时遍历两个链表，然后再遍历两个链表至相同结点。

空间复杂度： $O(1)$。

方法五：双指针：互换遍历

当链表 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。

时间复杂度： $O(m+n)$，两个指针同时遍历两个链表，然后再遍历两个链表至相同结点。

空间复杂度： $O(1)$。

5.实现示例

面以 Golang 为例，给出「双指针：互换遍历」的实现。

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {pA, pB := headA, headBfor 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
}

---

参考文献

160. 相交链表 - LeetCode
判断两个单链表是否相交及找到第一个交点原创 -CSDN