如何判断两个单向链表是否有相交，并找出交点

 

题比较简单，单向链表有交点意思就是交点后的节点都是一样的了

 

NODE* FindNode(NODE* pHead1, NODE* pHead2)
{
     NODE* p1 = pHead1;
     NODE* p2 = pHead2;
    int i = 1, j = 1, k = 0, f = 0;

    if(pHead1 == NULL || pHead2 == NULL)
    {
        return NULL;
    }

    while(p1->next != NULL)
    {
         p1 = p1->next;
         i++;
    }

    while(p2->next != NULL)
    {
         p2 = p2->next;
         j++;
    }

    if(p1 != p2)
    {
        return NULL;
    }
    else
    {
         p1 = pHead1;                // 1
         p2 = pHead2;

         f = fabs(i-j) //求绝对值的函数
        if(i > j)                    // 2
        {
            for(k=0; k<f; k++)
            {
                 p1 = p1->next;
            }
            while(p1 != p2)
            {
                 p1 = p1->next;
                 p2 = p2->next;
            }
            return p1;
        }
        else
        {
            for(k=0; k<f; k++)
            {
                 p2 = p2->next;
            }
            while(p1 != p2)
            {
                 p1 = p1->next;
                 p2 = p2->next;
            }
            return p1;
        }
    }
}

1，在第一次遍历完链表后，进行第二次遍历，需要把指针再次初始化；看见网上一些人给的例子没有再次初始化显然是错误的；再调用NULL的next不死才怪！

2，小优化。循环和判断，把判断放在外面；如果把i和j大小判断放在里面的话就意味着循环多少次，判断就执行多少次；当然这样做的唯一不足就是代码多了点；还有for循环之前的对f的赋值，有的为了简便直接放在for语句里面，不过同样道理，放在for循环里面，就执行了n次的fabs；拿出来赋值，只赋值一次就OK。