已知有两个链表，他们可能相交于某一点，求出该点。

方法1.对于第一个链表，每访问一个节点，对该节点做标记。访问第二个链表，如果该元素已经访问，则第一个这样的元素就是所求点。

由于两个链表都访问了一遍，因此时间复杂度O(m+n),空间复杂度O(m)或O(n)

方法2.我们定义节点的距离为节点到链表开始所经过的节点数。如果两个链表长度相同，则相交节点其在两个链表上的距离一定相等。对于长度不同的两个链表，我们可以采用对齐的方式，使其向长度短的链表对齐。这样就可以应用上面的思路。具体如下：

 

struct node
{
    int v;
    node *next;
};
/*
返回链表的长度
链表为空 返回0
*/
size_t listLen(node * p)
{
    size_t num = 0;
    while (p!=NULL)
    {
        num++;
        p = p->next;
    }
    return num;
}
// 如果找到了 则返回指针 指向公共节点
// 如果不存在 则返回空指针
node * findFirstCommenNode(node * pheada, node * pheadb)
{
    size_t lenA = listLen(pheada);
    size_t lenB = listLen(pheadb);

    node * plistA = pheada;
    node * plistB = pheadb;
    //调整长度
    //plistA 指向较长的一个
    if (lenA < lenB)
    {
        plistB = pheada;
        plistA = pheadb;
        size_t t = lenA;
        lenA = lenB;
        lenB = t;
    }
    while(lenA > lenB)
    {
        plistA = plistA->next;
        --lenA;
    }
    //一样长了
    //寻找公共节点
    while (plistA!=NULL && plistA != plistB)
    {
        plistA = plistA->next;
        plistB = plistB->next;
    }
    return plistA;
}

struct node{	int v;	node *next;};/*返回链表的长度链表为空 返回0*/size_t listLen(node * p){	size_t num = 0;	while (p!=NULL)	{		num++;		p = p->next;	}	return num;}// 如果找到了 则返回指针 指向公共节点// 如果不存在 则返回空指针node * findFirstCommenNode(node * pheada, node * pheadb){	size_t lenA = listLen(pheada);	size_t lenB = listLen(pheadb);	node * plistA = pheada;	node * plistB = pheadb;	//调整长度	//plistA 指向较长的一个	if (lenA < lenB)	{		plistB = pheada;		plistA = pheadb;		size_t t = lenA;		lenA = lenB;		lenB = t;	}	while(lenA > lenB)	{		plistA = plistA->next;		--lenA;	}	//一样长了	//寻找公共节点	while (plistA!=NULL && plistA != plistB)	{		plistA = plistA->next;		plistB = plistB->next;	}	return plistA;}

 

算法的空间复杂度O(1)，时间复杂度O(m+n)，效果不错吧。

如果链表中有环会怎么样呢？

上面的算法会死循环的。在求解链表长度的时候就会死循环了。但是这样的问题该如何解决呢。

首先的解决访问带环链表的问题。如果访问带环链表访问解决了，那么使用方法一就可以解决原问题，但是能不用优化到算法二的空间复杂度呢。算法二的思路还是很可取的，这里可不可以继续使用呢？

我们定义链表的长度为链表中节点的个数，如果链表相交，应该还是具有算法二的性质。因此，修改求取链表长度的算法，使用算法二。具体算法如下：

 

// 如果找到了 则返回指针 指向公共节点
// 如果不存在 则返回空指针
// pheada 指向第一个链表的头
// pheadb 指向第二个链表的头
node * findFirstCommenNode(node * pheada, node * pheadb)
{
    size_t lenA = listLen(pheada);
    size_t lenB = listLen(pheadb);

    node * plistA = pheada;
    node * plistB = pheadb;
    //调整长度
    //plistA 指向较长的一个
    if (lenA < lenB)
    {
        plistB = pheada;
        plistA = pheadb;
        size_t t = lenA;
        lenA = lenB;
        lenB = t;
    }
    while(lenA > lenB)
    {
        plistA = plistA->next;
        --lenA;
    }
    //一样长了
    //寻找公共节点
    while (lenA !=0 && plistA != plistB)
    {
        plistA = plistA->next;
        plistB = plistB->next;
        --lenA;//这里进行修改,免得进入环后死循环
    }
    return plistA;
}