楼主指真正意义上的链表相交，不仅data域相同，连地址也要一样。
可以这样做：
1.申请空间保存h1表
2.沿h1表的next/link域，将h1表的指针全部断掉
3.沿h2表向后扫描，扫描到最后的那个结点就是所求的第一相交结点
4.恢复h1表
这个算法的空间复杂度为O(n)，时间复杂度也是O(n)。
总觉得把空间复杂度降到O(1)为好，再想想看。

是个算法
不过好象有个问题,不能判断没有相交的

[此贴子已经被作者于2006-10-24 17:15:29编辑过]

这种破坏性的方法果然可以解决这个问题哦,
如果调整成线性时间复杂度好像不太可能,毕竟结点是任意的哦

假设链表1: e1->e2->e3->e4->e5
假设链表2: E1->E2->E3->E4->E5->E6->E7->e5(这里分两种情况,有e5和没有e5的)
1,申请个空表保存h1.
2.h1表的指针全部断掉,即e1,e2,e3,e4,e5,沿h2表扫描到最后一个对于有e5的是正确的,而如果没有e5,最后一个点就是E7了.
好象不能判断没有交点的结点

没考虑到//...再想想~

加个条件呢?
遍历h2时,到最后一个结点后再与保存的h1里的每个节点相比较,如果相同则相交,不同则没有交点,时间复杂度为总的时间复杂度为n(O)+n(O)=n(O);
...好像还是不行 ,保存的地址是变化过的?

[此贴子已经被作者于2006-10-24 18:33:03编辑过]

我有个想法，就是将两条链表首先连接在一起，既h2接到h1的尾部，然后通过一个从h1开始遍历该表，每个节点不都是一个指针吗？我们可以通过一个hash函数，将指针的指（不是指向其内容的值）传给它，计算出一张hash表，若是没有节点相交，也就是链表的每个节点都是从不同的内存地址分配的，即使其内容相同也不会发生碰撞，若是发生碰撞，可判断它们的地址一定相同，然后再测试其内容不就可以了，这样只要扫描一次两表就行，时间复杂度在O(N)内了，下面我贴上代码，若是我的算法有问题，请各位不指正，谢谢

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>

#define HASH_BUF 256

typedef struct node {
char data;
struct node *next;
} NODE, *PNODE;

PNODE create_list( void );
void display_list( PNODE h );
void destory_list( PNODE h );

int hash( PNODE p );

PNODE cross_cmp( PNODE h1, PNODE h2 );

int main() {
PNODE h1, h2;
PNODE pcross;

printf("Create list1\n");
h1 = create_list();
printf("Create list2\n");
h2 = create_list();

/* 在h2的尾部插入一个相交点，即h1的第二个节点 */
pcross = h2;
while( pcross->next )
pcross = pcross->next;
pcross->next = h1->next;

/* 获得相交指针 */
pcross = cross_cmp(h1,h2);
if(pcross)
printf("%p : %c\n", pcross, pcross->data);

getch();

return (int)0;
}

PNODE create_list( void ) {
char buf[80];
char *p = buf;

PNODE ret = (PNODE)malloc(sizeof(NODE));
PNODE np;
assert(ret);

memset(buf, (char)0, sizeof(char) * 80);

gets(buf);

np = ret;
while( *p ) {
np->data = *p++;
np->next = (PNODE)malloc(sizeof(NODE));
np = np->next;
assert(np);
}
np->next = (PNODE)0;

return ret;
}

void display_list( PNODE h ) {
PNODE p = h;
if( !p )
return;

while(p) {
printf("%c", p->data);
p = p->next;
}
}

void destory_list( PNODE h ) {
PNODE p = h, bak;
if( !p )
return ;
while(p) {
bak = p->next;
free(p);
p = bak;
}
}

int hash( PNODE p ) {
int plen = sizeof(PNODE) / 2;
int ret = 0;

ret = (int)(( (long)p << (plen * 8) ) >> (plen * 8));
ret %= (int)(pow(10.0,plen));

return ret;
}
PNODE cross_cmp( PNODE h1, PNODE h2 ) {
PNODE hash_container[HASH_BUF];
PNODE p = h1;

/* 记录连接点 */
PNODE pcptr;

int hcode;
int i;

/* 初始化Hash表 */
for(i = 0; i < HASH_BUF; ++i)
hash_container[i] = (PNODE)0;

while(p->next)
p = p->next;

pcptr = p;
/* 连接h1和h2 */
p->next = h2;
/* 重定向 */
p = h1;

/* 构造hash表，同时检验碰撞 */
while( p ) {
hcode = hash(p);
if( hash_container[hcode] == p && hash_container[hcode]->data == p->data) {
/* 断开两表的连接，返回交点 */
pcptr->next = (PNODE)0;
return p;
}
else
hash_container[hcode] = p;
p = p->next;
}

/* 无交点 */
pcptr->next = (PNODE)0;
return (PNODE)0;
}

哈希函数...good idea!!
偶没想到唉,不错//

俺微软出来的

可以先找到h1,h2的最后一个结点，比较两个结点的地址是否相同
若不相同，则h1,h2不相交，返回NULL
若相同，再按上面的方法即可

也可以用m,n分别记录h1,h2的长度
比较最后的结点
地址不相同，h1,h2不相交
相同，将较长的结点先向后(m-n)个结点
之后，可以用你之前的程序找到第一个相交的结点

因为是单链表 如果相交，则你下面的情形

a c e
b d m n
q w r

即相关交后，后面的结点既是h1的，又是h2的