面试100 35找出两个链表的第一个共同节点
一 问题描述：
找出两个单链表中的第一个公共节点。
解法1： 指针指向链表A的一个节点，然后在链表B上循环后移，直到发现与A链相同的节点，若是找不到，则A链后移。整个代码的时间复杂度为o(mn)
解法2： 我自己想到的一个办法，先将链表A的每一个指针的地址。作为hash映射到hash表中，然后遍历B链表，做同等的映射，直到第一次发现已经在
hash表中存在的节点。即为所求。
解法3： 最终的办法，因为是单链表，所以在第一个共同的节点之后，其余所有的节点都是共同的，所以为Y型。
所以不同的节点，只会在两个链表的最前方。根据此点，即可利用下面的小技巧，进行解决，时间复杂度为o(n)，但是需要两次遍历链表
求链表的长度。
考虑A链表的长度大于B链表，且长出B链表l个节点，那我们接下来就可以先遍历A链表的l个节点，然后即可以对链A和链B，一同向后移动，
直到发现两者共同指向的节点地址相同，即找到了所求。
二代码示例
#include <iostream>
#include <vector>
#include <iterator>
using namespace std ;
struct ListNode
{
ListNode * next ;
int data ;
} ;
ListNode head1 ; //头节点A
ListNode head2 ; //头节点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 ;
}
}
//建立共同的节点
void buildSameList( ListNode * h1 , ListNode * h2) //遍历stl数组，依次取得数据
{
ListNode * temp = (ListNode *)malloc(sizeof(ListNode)) ; //先申请一个节点
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
{ // 直到发现两者的节点地址相同，即找到所求
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建立共同的节点
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 ;
}