题解 | #两个链表的第一个公共结点#

参考题解理论：相同速度，相同路程，有公共结点，总会相遇

• 其实现主要逻辑是，构成环
  • 成环后的节点数 = 两链表节点数之和 # 两链表算成独立两条链表

代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    // pHead1 or pHead2 is null
    if(pHead1 == NULL || pHead2 == NULL)
    {
        return NULL;
    }
    
    // same speed, same length, so must be meet in after.
    struct ListNode * move1 = pHead1;
    struct ListNode * move2 = pHead2;
    while(move1->val != move2->val)
    {
        move1 = move1->next;
        move2 = move2->next;
        // no pn, when both are null
        if(move1 == NULL && move2 == NULL)
        {
            return NULL;
        }
        
        if(move1 == NULL)
        {
            move1 = pHead2;
        }
        if(move2 == NULL)
        {
            move2= pHead1;
        }
    }
    
    return move1;
}