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

核心思想

• 遍历两条链表，条件为
  • move1->val != move2->val
  • or
  • move1 != NULL && move2 != NULL
• 判断两个结点相等，则返回结点
• 两条链表后移
• move1 == NULL && move2 == NULL, 则代表相同长度，且无公共结点，返回NULL
• 模拟环形遍历，但是不能成环
  • if move1 == NULL; then
    • move1 = pHead2
  • if move2 == NULL; then
    • move2 = pHead1

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    // 判空
    if(pHead1 == NULL || pHead2 == NULL)
    {
        return NULL;
    }

    // 
    struct ListNode * move1 = pHead1;
    struct ListNode * move2 = pHead2;
    while(move1 != NULL && move2 != NULL)
    {
        // 共同结点
        if(move1 == move2)
        {
            return move1;
        }
        
        move1 = move1->next;
        move2 = move2->next;
        
        if(move1 == NULL && move2 == NULL)
        {
            return NULL;
        }
        
        if(move1 == NULL)
        {
            move1 = pHead2;
        }
        if(move2 == NULL)
        {
            move2 = pHead1;
        }
    }
    
    return NULL;
}