题意:
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。
方法:
双指针
思路:![]()
注意点:如果两链表没有公共部分,则会执行 a+b==b+a ,最后 p1==p2==null 而退出循环。
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *p1=pHead1,*p2=pHead2;
while(p1!=p2){//循环
p1=(p1==nullptr?pHead2:p1->next);
p2=(p2==nullptr?pHead1:p2->next);
}
return p1;
}
};
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号