社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
null
./**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *pa = headA,*pb = headB;
if(!pa || !pb)
{
return NULL;
}
struct ListNode *pa_last = NULL, *pb_last = NULL;
while(pa != pb)
{
if(pa_last == NULL && pa->next == NULL)/* Last of PA */
{
pa_last = pa;
}
if(pb_last == NULL && pb->next == NULL)/* Last of PB */
{
pb_last = pb;
}
if(pa_last && pb_last && pa_last != pb_last)
{
return NULL;/* end of two list not equal,No intersection */
}
pa = pa->next;
pb = pb->next;
if(pa == NULL){
pa = headB;
}
else if(pb == NULL){
pb = headA;
}
}
return pa;
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!