面試100 35找出兩個鏈表的第一個共同節(jié)點
一 問題描述：
找出兩個單鏈表中的第一個公共節(jié)點。
解法1： 指針指向鏈表A的一個節(jié)點，然后在鏈表B上循環(huán)后移，直到發(fā)現與A鏈相同的節(jié)點，若是找不到，則A鏈后移。整個代碼的時間復雜度為o(mn)
解法2： 我自己想到的一個辦法，先將鏈表A的每一個指針的地址。作為hash映射到hash表中，然后遍歷B鏈表，做同等的映射，直到第一次發(fā)現已經在
hash表中存在的節(jié)點。即為所求。
解法3： 最終的辦法，因為是單鏈表，所以在第一個共同的節(jié)點之后，其余所有的節(jié)點都是共同的，所以為Y型。
所以不同的節(jié)點，只會在兩個鏈表的最前方。根據此點，即可利用下面的小技巧，進行解決，時間復雜度為o(n)，但是需要兩次遍歷鏈表
求鏈表的長度。
考慮A鏈表的長度大于B鏈表，且長出B鏈表l個節(jié)點，那我們接下來就可以先遍歷A鏈表的l個節(jié)點，然后即可以對鏈A和鏈B，一同向后移動，
直到發(fā)現兩者共同指向的節(jié)點地址相同，即找到了所求。
二代碼示例
#include <iostream>
#include <vector>
#include <iterator>
using namespace std ;
struct ListNode
{
ListNode * next ;
int data ;
} ;
ListNode head1 ; //頭節(jié)點A
ListNode head2 ; //頭節(jié)點B
const int N = 10 ;
void buildList( ListNode * h , vector <int> &v) //遍歷stl數組，依次取得數據
{
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é)點
void buildSameList( ListNode * h1 , ListNode * h2) //遍歷stl數組，依次取得數據
{
ListNode * temp = (ListNode *)malloc(sizeof(ListNode)) ; //先申請一個節(jié)點
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) //先把長的鏈表，向后遍歷distance距離，然后同時向后遍歷A和B
{ // 直到發(fā)現兩者的節(jié)點地址相同，即找到所求
while(distance)
{
longlist = longlist->next ;
distance-- ;
}
while(longlist && shortlist)
{
if(longlist == shortlist) //應該是指針所指向的地址，即指針的值是相同的
{
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兩個單鏈表
buildSameList(&head1 , &head2 ) ; //對鏈表1和鏈表2建立共同的節(jié)點
visit(head1.next) ; //遍歷打印鏈表1和鏈表2
cout<<endl ;
visit(head2.next) ;
cout<<endl ;
int len1 = length(head1.next) ; //獲取鏈表1和鏈表2的長度
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 ;
}