缘由
鉴于本人长期使用ai写代码，手搓代码能力堪比成年草履虫，遂听从好友建议刷leetcode,然leetcode太难了QAQ，刷起来十分缓慢。今日写完jb物理实验报告打开leetcode 热题 100刷一下链表，发现了一道简单的链表题，即160.相交链表，然后便十分兴奋地打开开始做
题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
自定义评测：
评测系统 的输入如下（你设计的程序不适用此输入）：
intersectVa· - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案
我的想法
在经过一番苦思冥想之后，我也是写出了和官方一样的答案
就是遍历一遍链表headA，并将其存入哈希表中，然后遍历链表headB,对于遍历的每一个节点，判断该节点是否在哈希表内。
代码如下
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode *> visit;
ListNode *temp=headA;
while(temp!=nullptr)
{
visit.insert(temp);
temp=temp->next;
}
temp=headB;
while(temp!=nullptr)
{
if(visit.count(temp))
{
return temp;
}
temp=temp->next;
}
return nullptr;
}
};双指针解法
习惯性看题解，突然发现一个高赞题解
<(O0O)>
题解这样说：
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：
头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c 个节点；
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。
因此返回 A 即可。
代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A = headA, *B = headB;
while (A != B) {
A = A != nullptr ? A->next : headB;
B = B != nullptr ? B->next : headA;
}
return A;
}
};<(O0O)>
不知道是学得太少还是脑子是摆设，总之我是傻逼。
欸欸，还有很大进步空间……