stack解法:
两个链表先分别进栈
再依次出栈,从后向前遍历遇到第一个不相等的节点
再依次出栈,从后向前遍历遇到第一个不相等的节点
返回上一个相同节点即可
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1,ListNode* pHead2) {
ListNode* res = NULL;
if(!pHead1 || !pHead2)
return res;
stack<ListNode*> stack1;
stack<ListNode*> stack2;
while(pHead1){
stack1.push(pHead1);
pHead1 = pHead1->next;
}
while(pHead2){
stack2.push(pHead2);
pHead2 = pHead2->next;
}
if(stack1.top() != stack2.top())
return res;
while(stack1.size() != 0 && stack2.size() != 0){
res = stack1.top();
stack1.pop();
stack2.pop();
if(!stack1.empty() && !stack2.empty() && stack1.top() != stack2.top())
return res;
}
return res;
}
};

京公网安备 11010502036488号