idea：比较相同信息，首先想到用嵌套for循环解决，方法比较简单，不过时间复杂度高
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* p=headA; while(p!=NULL){ ListNode* q=headB; while(q!=NULL){ if(p==q) return p; else q=q->next; } p=p->next; } return NULL; } };
题解：
进阶：①哈希表法 idea：第一次接触哈希表，哈希表类似于一个将已有数据组转化为另一个具有下标的特殊数组，其中每个数据都可以在哈希表中找到“替身”，然后通过哈希表自带的函数操作，可以提高效率，降低时间复杂度
思路和算法
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 \textit{headA}headA，并将链表 \textit{headA}headA 中的每个节点加入哈希集合中。然后遍历链表 \textit{headB}headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果当前节点不在哈希集合中，则继续遍历下一个节点；
如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 \textit{headB}headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
如果链表 \textit{headB}headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>(); //创建名为visited的哈希表
ListNode temp = headA;
while (temp != null) { //一次循环将链表A中的每个结点存储到哈希表中
visited.add(temp); //visited对象的方法，将对应数据上传到哈希表中
temp = temp.next;
}
temp = headB;
while (temp != null) { //一次循环一一检验链表B中结点是否在哈希表中出现
if (visited.contains(temp)) { //检验temp是否出现在已有哈希表中
return temp;
}
temp = temp.next;
}
return null;
}
}
复杂度分析
时间复杂度：O(m+n)，其中 mm 和 nn 是分别是链表headA 和 headB 的长度。需要遍历两个链表各一次。
空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。
②双指针 idea：我感觉跟跟数学中的路径问题一联想不难理解，两个指针分别先后遍历AB和BA，如果不考虑相遇结点之后的相同部分，比如说从相遇开始到之前，A、B分别由2、3个结点，两个指针都走过5路径之后肯定会走到两个链表交会的结点上来。如果二者不相交，那么最后两个指针分别走到B和A的尾结点null，最终返回的也为null。
代码实现：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) { //貌似可以删去这句话，也可以过
return nullptr;
}
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next; //同时实现遍历和转接
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};
复杂度分析
时间复杂度：O(m+n)，其中 mm 和 nn 是分别是链表 headA 和headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
空间复杂度：O(1)。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
TRANSLATE with