🌿这是一个较为简单的链表题目，仅仅要注意判断链表都为空的情况。但看见评论区，才发现码农们充满浪漫的诗意

如果你们喜欢彼此，请携手一起走完剩下的旅程（将下面这个 while 块取消注释）。一路上，时而你踩着她的影子，时而她踩着你的影子。渐渐地，你变成了她,她也变成了你。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 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) {
        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），空间复杂度为O（1）

🌿另一种就是使用哈希表，这种方法需要额外的空间，空间复杂度就是O（m），其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点

unordered_set 是 C++ 标准库中的一个容器，属于 头文件。unordered_set 是一种 哈希表 容器，它存储的是 不重复 的元素，并且基于哈希表实现。元素的存储顺序是不固定的，即它不保持插入顺序，因此叫做 “unordered”（无序的）集合。与 set 不同，unordered_set 是通过哈希算法来快速查找和插入元素，因此查找操作的平均时间复杂度为 O(1)（常数时间），比 set 更高效，尤其是在数据量大的时候。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 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) {//通过哈希表来追踪headA的所有结点，并在遍历第二个链表时查找是否有相同的节点。
        unordered_set<ListNode *>visited;// 创建一个哈希集合，用于存储链表A的节点
        ListNode *temp = headA;  // temp 用于遍历链表A
        while(temp!=nullptr){
            visited.insert(temp); // 将链表A中的每个节点地址加入集合
            temp=temp->next;// 移动到下一个节点
        }
        temp=headB;
        while(temp!=nullptr){
            if(visited.count(temp)){
                return temp;//如果链表B中存在相同结点返回相同结点temp
            }
            temp=temp->next;
        }
        return nullptr;
            }
};