链表:找出两个链表的相交节点

这个问题我们现在只考虑是2个不带环链表相交,如图:

那么我们如何找到这个节点d那？
我们可以定义2个头节点head1, head2,让它们同时走下去，如果head1 == head2的话，就说明找到了d点，然而很明显，这是假设list1与list2长度相同的情况下，所以我们需要先遍历一次2个链表，得出2个链表的长度length1，length2,让长的先走|length2-length1|步，这样就可以保证2个同时到达d点。

当然还要排除一种情况，那就是给出的2个链表不相交。
代码如下：

ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {



        ListNode *c_head1 = pHead1;
        ListNode *c_head2 = pHead2;
        int length1 = 1;
        int length2 = 1;

        if ( NULL == pHead1 || NULL == pHead2 ){

            return NULL;
        }
        //遍历一次得出2个链表的长度
        while ( c_head1 != NULL ){

            length1++;
            c_head1 = c_head1->next;
        }
        while ( c_head2 != NULL ){

            length2++;
            c_head2 = c_head2->next;
        }
        //求出length1-length2,结果的正负表示谁的长度长谁先走
        length2 = length1 - length2;

        if ( length2 > 0 ){

            while ( j-- ){
                pHead1 = pHead1->next;
            }
        }
        else if (length2 < 0){
                j = -j;
                while (j--)
                pHead2 = pHead2->next;
        }

        //2个同时走，相等则找到d点，如果任意一个为NULL，则表示没有相交节点
        while ( pHead1 && pHead2 && pHead1 != pHead2 ){

            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        if ( pHead1 == NULL || pHead2 == NULL){

            return NULL;
        }
        else return pHead1;
    }

当然还有另一种办法：