题目描述：
输入两个链表，找出它们的第一个公共结点。
测试用例：
1）功能测试（输入的链表有公共节点：公共节点在链表的中间、尾部、头部；输入的链表没有公共的节点）
2）特殊输入测试（输入的链表头节点尾nullptr）
解题思路：
1）使用辅助栈 时间复杂度O(m+n)，空间复杂度也是O(m+n)
分别把两个链表的节点放入两个栈中，这样的链表的尾节点就位于两个栈的栈顶，接下来比较两个栈的栈顶是否相同。如果相同，弹出比较下一个尾节点，直到找到最后一个尾节点
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1==nullptr || pHead2==nullptr)
return nullptr;
stack<ListNode*> nodes1,nodes2;
ListNode* pNode = pHead1;
//把第一个链表存入栈中
while(pNode!=nullptr){
nodes1.push(pNode);
pNode = pNode->next;
}
//把第二个链表存入栈中
pNode = pHead2;
while(pNode!=nullptr){
nodes2.push(pNode);
pNode = pNode->next;
}
//寻找最后一个公共的节点
pNode=nullptr;
while((!nodes1.empty()) && (!nodes2.empty())){//当两者都不为空的时候进入循环 //ok
//while((nodes1.size()!=0) && (nodes2.size()!=0)){ //ok
if(nodes1.top()==nodes2.top())
pNode=nodes1.top();
nodes1.pop();
nodes2.pop();
}
return pNode;
}
};
2）不使用辅助空间，时间复杂度O(m+n)
分别遍历两个链表获得两个链表的长度，较长的链表先走若干步（长链表-短链表，以保证两者同时到达尾部）
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1==nullptr || pHead2==nullptr)
return nullptr;
int lenght1 = getLength(pHead1);
int lenght2 = getLength(pHead2);
int lengthDiff = lenght1 - lenght2;
ListNode* pHeadLong = pHead1;
ListNode* pHeadShort = pHead2;
if(lenght1<lenght2){
pHeadLong = pHead2;
pHeadShort = pHead1;
lengthDiff = lenght2 - lenght1;
}
//长的链表先走
for(int i=0;i<lengthDiff;i++)
pHeadLong = pHeadLong->next;
//寻找第一个相等的节点
while(pHeadLong!=nullptr && pHeadShort!=nullptr && pHeadLong!=pHeadShort){
pHeadLong = pHeadLong->next;
pHeadShort = pHeadShort->next;
}
if(pHeadLong==pHeadShort) //如果不相等，则说明没有公共的节点
return pHeadLong;
return nullptr; //没有公共的节点
}
int getLength(ListNode* pHead){
int length=0;
ListNode* pNode = pHead;
while(pNode!=nullptr){
length++;
pNode = pNode->next;
}
return length;
}
};
3)使用map，时间复杂度O(nlog(n))
classSolution {
public:
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
map<ListNode*, int> m;
ListNode *p = pHead1;
while(p != NULL) {
m[p] = 1;
p = p->next;
}
p = pHead2;
while(p != NULL) {
if(m[p]) {
return p;
}
p = p->next;
}
return NULL;
}
};