仿网站,郑州营销型网站建设,泉州网站设计制作,wordpress 带用户中心题干
LCR 023. 相交链表
的头节点 headA 和 headB #xff0c;请找出并返回两个单链表相交的起始节点。如果两个链表没有交点#xff0c;返回 null 。
图示两个链表在节点 c1 开始相交#xff1a; 题目数据 保证 整个链式结构中不存在环。
注意#xff0c;函数返回结果…题干
LCR 023. 相交链表
的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
题解双指针法
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {};
};ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (!headA || !headB) return nullptr;ListNode *first headA;ListNode *second headB;while (first ! second) {first (first ? first-next : headB);second (second ? second-next : headA);}return first;
}
解析
数学解释
假设
链表 A 的非相交部分长度为 lenA - lenC。链表 B 的非相交部分长度为 lenB - lenC。
当两个指针重定向后它们走过的总距离分别是
first 走过的总距离(lenA - lenC) lenC (lenB - lenC) lenA lenB - lenCsecond 走过的总距离(lenB - lenC) lenC (lenA - lenC) lenB lenA - lenC
由于 (lenA lenB - lenC) 和 (lenB lenA - lenC) 是相同的所以两个指针最终会在相交节点处相遇。
其实互相抵消掉重叠的lenc各自走的长度就是lenA lenB
个人理解每次移动指针就算一个距离双方移动的距离都是AB这个算法不是一定会在相交点结束而是走的距离一样一定都会在两个链表的最后一个节点停止。只不过如果相交了两个链的最后一个点都是相交点如果没相交那就都是nullptr。我的说法忽略了重复节点的遍历因为从数学的角度上可以直接互相抵消这段距离。
