题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
算法思想一：双指针
解题思路：
使用两个指针 a，b 分别指向两个链表 pHead1，pHead2的头结点，然后同时分别逐结点遍历，当 a 到达链表 pHead1的末尾时，重新定位到链表 pHead2的头结点；当 b 到达链表 pHead2 的末尾时，重新定位到链表 pHead1的头结点。当双指针相遇时，所指向的结点就是第一个公共结点
图解：
代码展示：
Python版本
class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): # write code here a = pHead1 b = pHead2 # 当两者相同则是第一个公共节点 while a!=b: # a从pHead1遍历完再遍历pHead2 a = a.next if a else pHead2 # b从pHead2遍历完再遍历pHead1 b = b.next if b else pHead1 return a
复杂度分析
时间复杂度O(M+N)：M, N分别表示 pHead1， pHead2的链表长度，最差情况下需要遍历完两个链表
空间复杂度O(1)：仅使用常数级变量空间
算法思想二：集合set
解题思路：
做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可代码展示：
JAVA版本
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//创建集合set
Setset = new HashSet<>();
//先把链表1的结点全部存放到集合set中
while (pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
//然后访问链表2的结点，判断集合中是否包含链表2的结点，如果包含就直接返回
while (pHead2 != null) {
if (set.contains(pHead2))
return pHead2;
pHead2 = pHead2.next;
}
//如果集合set不包含链表2的任何一个结点，说明没有交点，直接返回null
return null;
}
} 复杂度分析
时间复杂度O(M+N)：M, N分别表示 pHead1， pHead2的链表长度，最差情况下需要遍历完两个链表
空间复杂度O(M)：需要额外集合空间存储 pHead1 结点
算法思想三：统计两个链表的长度
解题思路：
还可以先统计两个链表的长度，如果两个链表的长度不一样，就让链表长的先走，直到两个链表长度一样，这个时候两个链表再同时每次往后移一步，看节点是否一样，如果有相等的，说明这个相等的节点就是两链表的交点，否则如果走完了还没有找到相等的节点，说明他们没有交点，直接返回null即可 图解：
代码展示：
JAVA版本
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//统计链表A和链表B的长度
int lenA = length(pHead1), lenB = length(pHead2);
//如果节点长度不一样，节点多的先走，直到他们的长度一样为止
while (lenA != lenB) {
if (lenA > lenB) {
//如果链表A长，那么链表A先走
pHead1 = pHead1.next;
lenA--;
} else {
//如果链表B长，那么链表B先走
pHead2 = pHead2.next;
lenB--;
}
}
//然后开始比较，如果他俩不相等就一直往下走
while (pHead1 != pHead2) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
//走到最后，最终会有两种可能，一种是headA为空，
//也就是说他们俩不相交。还有一种可能就是headA
//不为空，也就是说headA就是他们的交点
return pHead1;
}
//统计链表的长度
private int length(ListNode node) {
int length = 0;
while (node != null) {
node = node.next;
length++;
}
return length;
}
} 复杂度分析
时间复杂度O(M+N)：M, N分别表示 pHead1， pHead2的链表长度，最差情况下需要遍历完两个链表
空间复杂度O(1)：仅使用常数级空间变量
查看3道真题和解析