### 这道题分两种情况讨论：链表是否存在环（询问面试官）。一些额外的说明：两个链表，第一个是链表A，长度为m，第二个是链表B，长度为n。
---
#### 无环
**第一种方法**：朴素的方法是将以链表A的每一个节点为key，对着链表B做一次遍历，直到找到第一个公共节点，或者没有公共节点，直接返回nullptr。时间复杂度为O(mn)，空间复杂度为O(1)。这种方法的一种直接改进是使用哈希表保存链表A的每一个节点，因为之前的方法主要是查找消耗时间，这样做是以空间换时间（哈希表需要O(m)的空间保存），时间复杂度为O(m + n)。
**第二种方法**：不使用额外空间，但是时间也是O(m + n)。先遍历两个链表（因为没有环，所以直接遍历就可以），求出它们的长度 m 和 n。然后长的链表先走 | m - n | 步，之后再同时向前走，直到找到第一个公共节点。
下面实现第二种方法：
```
// 返回值：有公共节点，则返回第一个，否则，返回nullptr
SList* findFirstCommonNode(SList *list1, SList *list2)
{
unsigned int lengthOfList1 = getListLength(list1);
unsigned int lengthOfList2 = getListLength(list2);
SList *longList = list1, *shortList = list2;
unsigned int deltaOfLength = lengthOfList1 - lengthOfList2;
if (lengthOfList1 < lengthOfList2) {
longList = list2;
shortList = list1;
deltaOfLength = lengthOfList2 - lengthOfList1;
}
// 长链表先走 deltaOfLength 步
for (unsigned int i = 0; i < deltaOfLength; ++i) {
longList = longList->m_next;
}
while ( (longList != nullptr) &&
(shortList != nullptr) &&
(longList != shortList)) {
longList = longList->m_next;
shortList = shortList->m_next;
}
return longList;
}
// 求链表长度
unsigned int getListLength(SList *list)
{
unsigned int length = 0;
while (list != nullptr) {
++length;
list = list->m_next;
}
return length;
}
```
#### 不知道是否有环
这种情况我们需要先[判断链表是否有环](https://www.kancloud.cn/persuez/algorithm/858057)。
1. 两个链表都没有环， 按上面无环的算法走；
2. 一个有环，一个无环，这两个链表不可能相交，返回nullptr；
3. 两个都有环，此时两条链表如果相交，那么一定共享这个环。但如果相交的话，我们取哪个作为第一个公共节点呢？有人取下面的公共节点pos2作为两个链表的最后一个节点，然后用无环的方法求第一个公共节点，但我觉得似乎也没有什么特别意义。所以我们的主要任务就判断这个环是不是共有的就好了。我们在判断是否有环时返回两个链表的相遇点，记为pos1，pos2。然后我们在pos1点设置快慢指针，慢指针每次走一步，快指针每次走两步，那么在它们再次相遇时慢指针（或者快指针和快指针的m_next）一定遍历了整个环，而这个环是共享的，所以如果pos2也在这个环中，那么这两个链表就是相交的。（这里相当提供了一种方法遍历环）