昨天有幸获得淘宝算法工程师面试资格，就去打了把酱油。先是被错领着进行了测试开发的面试，然后才进行了算法的面试，很悲催呀。测试开发的面试比较简单，问了最大字段和、非递归中序遍历二叉树问题，这个我会再讨论一下的，算法面试问的就是这个链表题，不过他只让我判断是否有交点，我当时给出了两种思想：复杂的就是一个一个的判断，复杂度O(m*n)，稍微便捷点的就是判断最后一个节点是否相等，复杂度O(m+n)。他问我如果这两个链表很长该怎么办，我假设知道了这两个链表的长度(可能建立时进行了计数)，然后呢？然后我就没有了然后了。。。。回来仔细想了下，有了新的思路：知道了两个链表的长度len1,len2，那么先让长的链表向后遍历abs(len1-len2)，再进行同时遍历并一对一比较，这样的话复杂度为O(max(m,n))。
         今天讨论O(m+n)的算法，代码如下：

/**//*===========================================================================
* Function name:   FindNode   
* Parameter:       pHead1,pHead2分别为待判断的链表头结点  
* Precondition:    两个链表已经建立   
* Postcondition:   NONE
* Description:     判断两个单向链表是否有交点并返回交点    
* Return value:    交点      
* Author:          Trojan,  [4/16/2011]
===========================================================================*/
NODE* FindNode(NODE* pHead1, NODE* pHead2)
{
    NODE* p1 = pHead1;
    NODE* p2 = pHead2;
    int i = 1, j = 1, k = 0, f = 0;

    if(pHead2 == 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
    {
        
        f = fabs(i - j);
        if(i > j)                    
        {
            p1 = pHead1;
            p2 = pHead2;
        }
        else
        {
            p1 = pHead2;
            p2 = pHead1;
        }
        for(k=0; k<f; k++)
        {
            p1 = p1->next;
        }
        while(p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
}