面試100 35找出兩個(gè)鏈表的第一個(gè)共同節(jié)點(diǎn)
一 問(wèn)題描述：
找出兩個(gè)單鏈表中的第一個(gè)公共節(jié)點(diǎn)。
解法1： 指針指向鏈表A的一個(gè)節(jié)點(diǎn)，然后在鏈表B上循環(huán)后移，直到發(fā)現(xiàn)與A鏈相同的節(jié)點(diǎn)，若是找不到，則A鏈后移。整個(gè)代碼的時(shí)間復(fù)雜度為o(mn)
解法2： 我自己想到的一個(gè)辦法，先將鏈表A的每一個(gè)指針的地址。作為hash映射到hash表中，然后遍歷B鏈表，做同等的映射，直到第一次發(fā)現(xiàn)已經(jīng)在
hash表中存在的節(jié)點(diǎn)。即為所求。
解法3： 最終的辦法，因?yàn)槭菃捂湵恚栽诘谝粋€(gè)共同的節(jié)點(diǎn)之后，其余所有的節(jié)點(diǎn)都是共同的，所以為Y型。
所以不同的節(jié)點(diǎn)，只會(huì)在兩個(gè)鏈表的最前方。根據(jù)此點(diǎn)，即可利用下面的小技巧，進(jìn)行解決，時(shí)間復(fù)雜度為o(n)，但是需要兩次遍歷鏈表
求鏈表的長(zhǎng)度。
考慮A鏈表的長(zhǎng)度大于B鏈表，且長(zhǎng)出B鏈表l個(gè)節(jié)點(diǎn)，那我們接下來(lái)就可以先遍歷A鏈表的l個(gè)節(jié)點(diǎn)，然后即可以對(duì)鏈A和鏈B，一同向后移動(dòng)，
直到發(fā)現(xiàn)兩者共同指向的節(jié)點(diǎn)地址相同，即找到了所求。
二代碼示例
#include <iostream>
#include <vector>
#include <iterator>
using namespace std ;
struct ListNode
{
ListNode * next ;
int data ;
} ;
ListNode head1 ; //頭節(jié)點(diǎn)A
ListNode head2 ; //頭節(jié)點(diǎn)B
const int N = 10 ;
void buildList( ListNode * h , vector <int> &v) //遍歷stl數(shù)組，依次取得數(shù)據(jù)
{
vector<int>::iterator iter = v.begin() ;
for(;iter < v.end() ; iter++)
{
ListNode * temp = (ListNode *)malloc(sizeof(ListNode)) ;
temp->data = *iter ;
temp->next = h->next ;
h->next = temp ;
}
}
//建立共同的節(jié)點(diǎn)
void buildSameList( ListNode * h1 , ListNode * h2) //遍歷stl數(shù)組，依次取得數(shù)據(jù)
{
ListNode * temp = (ListNode *)malloc(sizeof(ListNode)) ; //先申請(qǐng)一個(gè)節(jié)點(diǎn)
temp->data = 3 ;
temp->next = h2->next ;
h2->next = temp ;
//讓h2的next指針，指向h1
temp->next = h1->next->next->next->next->next ;
}
int length(ListNode * p)
{
int len = 0 ;
while(p)
{
len++ ;
p = p->next ;
}
return len ;
}
void visit(ListNode * p)
{
while(p)
{
cout<<p->data<<" " ;
p = p->next ;
}
}
void findsamenode(ListNode * longlist ,ListNode * shortlist , int distance) //先把長(zhǎng)的鏈表，向后遍歷distance距離，然后同時(shí)向后遍歷A和B
{ // 直到發(fā)現(xiàn)兩者的節(jié)點(diǎn)地址相同，即找到所求
while(distance)
{
longlist = longlist->next ;
distance-- ;
}
while(longlist && shortlist)
{
if(longlist == shortlist) //應(yīng)該是指針?biāo)赶虻牡刂罚粗羔樀闹凳窍嗤?nbsp;
{
cout<<longlist->data ;
break ;
}
longlist = longlist->next ;
shortlist = shortlist->next ;
}
}
int main()
{
head1.next = 0 ;
head1.data = 1;
head2.next = 0 ;
head2.data = 1;
vector <int> v ;
for(int i = 0 ; i < N ;i++)
v.push_back(i) ;
buildList(&head1 , v) ; //建立1和2兩個(gè)單鏈表
buildSameList(&head1 , &head2 ) ; //對(duì)鏈表1和鏈表2建立共同的節(jié)點(diǎn)
visit(head1.next) ; //遍歷打印鏈表1和鏈表2
cout<<endl ;
visit(head2.next) ;
cout<<endl ;
int len1 = length(head1.next) ; //獲取鏈表1和鏈表2的長(zhǎng)度
int len2 = length(head2.next) ;
cout<<len1<<" "<<len2<<endl;
if(len1 >= len2)
findsamenode(head1.next , head2.next , len1-len2) ;
else
findsamenode(head2.next , head1.next , len2-len1) ;
system("pause") ;
return 0 ;
}