1 题目及要求
1.1 题目描述
输入两个链表，找出他们的第一个公共节点。
2 解答
2.1 代码
#include <iostream>
#include <stack>
using namespace std;
// 链表节点类
struct ListNode{
int val;
ListNode *next;
ListNode(int x = 0):val(x),next(nullptr){}
};
// 扫描 o(m*n)时间
ListNode* firstCommonNode1(ListNode *head1, ListNode *head2){
if(!(head1&&head2)) return nullptr;
for(ListNode* np;head1;head1 = head1->next)
for(np = head2;np;np = np->next)
if(np==head1) return np;
return nullptr;
}
// 栈实现,从尾到头逐个比较,直到最后一个相同的 o(m+n)时间, o(m+n)空间
ListNode* firstCommonNode2(ListNode *head1, ListNode *head2){
if(!(head1&&head2)) return nullptr;
stack<ListNode*> st1,st2;
for(;head1;head1 = head1->next) st1.push(head1);
for(;head2;head2 = head2->next) st2.push(head2);
while(!(st1.empty() || st2.empty()) && st1.top()==st2.top()){
head1 = st1.top();
st1.pop();
st2.pop();
}
return head1;
}
// 循环实现, o(m+n)时间, o(1)空间
ListNode* firstCommonNode3(ListNode *head1, ListNode *head2){
if(!(head1&&head2)) return nullptr;
ListNode *np1 = head1, *np2 = head2;
while(np1!=np2){
np1 = np1 ? np1->next : head2;
np2 = np2 ? np2->next : head1;
}
return np1;
}
int main(){
ListNode h1[] = {1,2,3,4,5,6,7}, h2[] = {8,9};
int s1 = sizeof(h1)/sizeof(ListNode), s2 = sizeof(h2)/sizeof(ListNode);
for(int k1(0);k1<s1-1;++k1) h1[k1].next = h1+k1+1;
for(int k2(0);k2<s2-1;++k2) h2[k2].next = h2+k2+1;
// 这里从第5个节点(val = 5)开始公用节点
h2[s2-1].next = h1+4;
auto np1 = firstCommonNode1(h1,h2);
auto np2 = firstCommonNode2(h1,h2);
auto np3 = firstCommonNode3(h1,h2);
cout << (np1?np1->val:0) << endl;
cout << (np2?np2->val:0) << endl;
cout << (np3?np3->val:0) << endl;
return 0;
}
