题目

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。





答题

假设链表分别为 A 和 B，对应长度为 m 和 n。

根据 A 和 B 是否 带环 以及是否有 交点，可以分下面几种情况：

1. A 和 B 没有交点，则无论 A 和 B 是否有环；只要分别遍历两个链表，确定没有共同点即可。

2. A 和 B 有交点，且 不带环；则 只要分别遍历两个链表，找到第一个交点即可完成。

3. A 和 B 有交点，且带环；根据交点是否在环上，又可以分为 2 种情况：

4. 如果交点不在环上，只要分别遍历两个链表，找到第一个交点即可完成

5. 如果交点在环上，则 A 和 B 在环上的 入点 都可被认为是 合并点。



解题思路

1. 定义 HashSetA 和 HashSetB 用来保存每个节点的引用或地址

2. 遍历链表 A 的每个节点，并检查该节点是否已经在 HashSetA 里边

• 假如 当前节点 已经在 HashSetA 里边，则说明链表 A 带环且入环节点为当前节点；保存当前入环节点并结束遍历

• 假如 当前节点 不在 HashSetA 里边，则插入该节点到 HashSetA 里边。

1. 遍历链表 B 的所有节点，并检查该节点是否可以在 HashSetA 里边找到

• 假如可以找到，则说明两个链表有交叉点，且交叉点为当前节点（假如链表 A 带环，则交叉点也可以为链表 A 的入环点）

• 假如没有找到，则继续检查该节点是否已经在 HashSetB 里边

• 假如 当前节点 已经在 HashSetB 里边，则说明链表 B 带环且两个链表没有交叉点；结束遍历

• 假如 当前节点 不在 HashSetB 里边，则插入该节点到 HashSetB 里边。

1. 返回交叉点或者 null



时间复杂度

由于只要分别遍历一遍两个链表 A 和 B，所有时间复杂度为 O(max(m, n))

空间复杂度

需要两个 Hash 表来保存每个节点的引用或地址，所以空间复杂度为 O(max(m, n))

伪代码实现

Def HashSet setA;  // 保存链表 A 的所有节点引用（地址）
Def HashSet setB;  // 保存链表 B 的所有节点引用（地址）
def resutlNode = null;
def enterPointA = null; // 保存链表 A 的入环节点引用
def node = A.head;
while node != null;
	if node is in setA; // 找到 A 环的入口点
		enterPointA = node;
		break;
	else
		setA.add(node);
	end // if
 	node = node.next;
end // while
node = B.head;
while node != null;
	if node is in setA; // 找到交点
		if enterPointA == null; // 不带环
			resutlNode = node;
			break;
		else  // 带环
			resultNode = node;  // 选择 B 的入口点作为合并点
			// resultNode = enterPointA;  // 选择 A 的入口点作为合并点
			break;
		end // if
	else // 不是交点
		if node is in setB; // 找到 B 环的入口点
			resutlNode = null； // 结束循环，没有交点
			break；
		else
			setB.add(node);
		end // if
	end // if
	node = node.next;
end // while
 
return resultNode;