題目描述
輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。
思路
兩個(gè)鏈表如果有交點(diǎn)，那么只有兩種情況
1.呈"Y"字形渡处，重復(fù)后的節(jié)點(diǎn)連成一條
2.呈“I”字形，一條鏈表是另一條的一部分
不管什么形式祟辟，這兩條鏈表的后面一定是重合的医瘫，那么我把兩條鏈表分別保存在棧結(jié)構(gòu)中，然后同時(shí)出棧川尖，直到兩邊的棧頂不相等時(shí)登下，那么前一個(gè)節(jié)點(diǎn)就是公共節(jié)點(diǎn)茫孔。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
stack<ListNode*> stack1;
stack<ListNode*> stack2;
while(pHead1 != NULL)
{
stack1.push(pHead1);
pHead1 = pHead1->next;
}
while(pHead2 != NULL)
{
stack2.push(pHead2);
pHead2 = pHead2->next;
}
ListNode* sharepHead = NULL;
//６Ｔ！缰贝！注意這里的判斷馍悟，一定要加上(!stack1.empty())&&(!stack2.empty())
while((!stack1.empty())&&(!stack2.empty())&&(stack1.top()
== stack2.top()))
{
sharepHead = stack1.top();
stack1.pop();
stack2.pop();
}
return sharepHead;
}
};
