Alangy's Blog
这个人很懒，什么都没有写
Toggle navigation
Alangy's Blog
首页
LeetCode刷题记录
开发
关于我
文章归档
标签
相交链表
2023-02-26 16:55:58
50
0
0
admin
剑指 Offer 52. 两个链表的第一个公共节点 https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/ 虽然标为【简单】，但其实进阶做法较有技巧。其和链表成环一样，都能想到双指针。但是本题双指针的取巧性更强。 具体而言，假设链表A的私有部分长为a，链表B的私有部分长为b，二者的公共部分（如有）长度为c。 在aPtr走到尽头时，走了长度为a+c,此时只要将其接到B上继续往下走，走长度b时，总步数为a+c+b。而bPtr走到尽头时，接到A上继续往下走长度为a时，总步数也为a+c+b，即二者重合时【而且】此时二者都在第一个公共节点上。 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; } };
上一篇:
主定理
下一篇:
a>b Problem
0
likes
50
Weibo
Wechat
Tencent Weibo
QQ Zone
RenRen
Submit
Sign in
to leave a comment.
No Leanote account?
Sign up now.
0
comments
More...
Table of content
admin
No Leanote account? Sign up now.