本文共 1254 字，大约阅读时间需要 4 分钟。

我的解法：hashset(效率不高)

思想：

复杂度：

​ ●时间：O(M + N)，遍历两个链表

​ ●空间：O(M + N)，利用set存储

代码：

​ 一开始我居然是用A放一个B放一个来做的，发现这样完全不可行，因为可能A到尾了，B还没到相交节点

class Solution {
   public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
           if(headA == NULL || headB == NULL)            return 0;        unordered_set
   
    set_ListNode;        //先把A放入set        while(headA != NULL){
               set_ListNode.insert(headA);            headA = headA->next;        }        //在set中查找B的每一个节点，查到了就返回        while(headB != NULL){
               if(set_ListNode.find(headB) != set_ListNode.end())                return headB;            headB = headB->next;        }        return NULL;    }};
   

解法2：双指针

思想：

两个链表长度分别为L1+C、L2+C， C为公共部分的长度，按照楼主的做法： 第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相遇了

复杂度：

​ ●时间：O(M + N)

​ ●空间：O(1)

代码：

class Solution {
   public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
           //不用特判NULL，如果不相遇两人会同时走到末尾即NULL，结束循环，返回NULL        ListNode *node1 = headA;        ListNode *node2 = headB;                while (node1 != node2) {
               node1 = node1 != NULL ? node1->next : headB;            node2 = node2 != NULL ? node2->next : headA;        }        return node1;    }};