题目来源
160. 相交链表 - 力扣（LeetCode）
题目描述
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交：编辑
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
题目限制
使用最优解做完此题
要求时间复杂度O(n+m)
空间复杂度O(1)
思路分析
这道题要找两个无环单链表的相交起始节点。常规暴力法是对链表A每个节点，遍历链表B看是否有相同节点，时间复杂度为\(O(mn)\)（\(m\)、\(n\)分别为两链表长度），效率低。高效思路是利用双指针，让两指针分别从两链表头出发，当一个指针到达链表尾时，重新指向另一链表头继续走，这样两指针走过相同总路程，若相交，会在相交起始节点相遇，若不相交，最终都会走到null，时间复杂度\(O(m + n)\)，通过此方法可高效解决该问题 。
具体代码
/*** 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||!headB)return nullptr;ListNode* a=headA;ListNode* b=headB;//如果没有香蕉的 到最后两个人都走到同一个地址但是 是空指针nullptr //判断条件写a=b时结束 返回香蕉的值 或者返回空while(a!=b){a=a?a->next:headB;b=b?b->next:headA;}return a;}
};这段 C++ 代码定义了 Solution 类中的 getIntersectionNode 函数，用于找出两个单链表 headA 和 headB 的相交节点。首先检查 headA 和 headB 是否为空，若有一个为空则直接返回 nullptr，因为空链表不存在相交节点。接着，定义两个指针 a 和 b 分别指向 headA 和 headB。通过一个 while 循环，只要 a 和 b 不相等就持续循环。在每次循环中，a 指针移动到下一个节点，如果 a 已经到达链表末尾（即 a 为 nullptr），则将 a 重新指向 headB；同理，b 指针移动到下一个节点，若 b 到达链表末尾则重新指向 headA。这样做的目的是让两个指针走过相同的距离，从而找到相交节点。当 a 和 b 相等时，循环结束，此时 a （或 b）即为相交节点，返回 a。若两个链表不相交，最后 a 和 b 都会指向 nullptr 并结束循环，同样返回 a（即 nullptr） 。