【C++】LeetCode：LCR 023. 相交链表

题干

LCR 023. 相交链表
的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。假如两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：

标题数据 包管 整个链式结构中不存在环。
注意，函数返回效果后，链表必须 保持其原始结构 。
题解：双指针法

1. struct ListNode {
2.     int val;
3.     ListNode *next;
4.     ListNode(int x) : val(x), next(nullptr) {};
5. };
7. ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
8.     if (!headA || !headB) return nullptr;
10.     ListNode *first = headA;
11.     ListNode *second = headB;
13.     while (first != second) {
14.         first = (first ? first->next : headB);
15.         second = (second ? second->next : headA);
16.     }
18.     return first;
19. }

复制代码

剖析：

数学表明

假设：

• 链表 A 的非相交部分长度为 lenA - lenC。
  
• 链表 B 的非相交部分长度为 lenB - lenC。
  

当两个指针重定向后，它们走过的总隔断分别是：

• first 走过的总隔断：(lenA - lenC) + lenC + (lenB - lenC) = lenA + lenB - lenC
  
• second 走过的总隔断：(lenB - lenC) + lenC + (lenA - lenC) = lenB + lenA - lenC
  

由于 (lenA + lenB - lenC) 和 (lenB + lenA - lenC) 是雷同的，以是两个指针终极会在相交节点处相遇。
实在，相互抵消掉重叠的lenc，各自走的长度就是lenA + lenB
个人明确：每次移动指针就算一个隔断，双方移动的隔断都是A+B，这个算法不是肯定会在相交点竣事，而是走的隔断一样，肯定都会在两个链表的末了一个节点制止。只不外，假如相交了，两个链的末了一个点都是相交点，假如没相交那就都是nullptr。我的说法忽略了重复节点的遍历，由于从数学的角度上可以直接相互抵消这段隔断。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金