编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在节点 c1 开始相交。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
详见：https://leetcode.com/problems/intersection-of-two-linked-lists/description/
方法一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr)
{
return nullptr;
}
stack<ListNode*> stk1;
stack<ListNode*> stk2;
while(headA)
{
stk1.push(headA);
headA=headA->next;
}
while(headB)
{
stk2.push(headB);
headB=headB->next;
}
if(stk1.top()!=stk2.top())
{
return nullptr;
}
ListNode *common=nullptr;
while(!stk1.empty()&&!stk2.empty()&&stk1.top()==stk2.top())
{
stk1.pop();
common=stk2.top();
stk2.pop();
}
return common;
}
};
方法二：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr)
{
return nullptr;
}
ListNode* head1=headA;
ListNode* head2=headB;
int n=0;
while(head1)
{
++n;
head1=head1->next;
}
while(head2)
{
--n;
head2=head2->next;
}
if(head1!=head2)
{
return nullptr;
}
head1=n>0?headA:headB;
head2=head1==headA?headB:headA;
n=abs(n);
for(int i=0;i<n;++i)
{
head1=head1->next;
}
while(head1!=head2)
{
head1=head1->next;
head2=head2->next;
}
return head1;
}
};