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

这道题有些面向结果编程了qaq，写出来后好多测试点过不去，然后就面向结果了qaq

我的思路是，从链表的尾部往前比较两个链表各自的节点，如果一开始节点的地址不同说明是不同的节点，则两个链表没有共同的节点；如果一开始节点的地址是相同的，然后往前遍历的过程中发现了有不同地址的节点，则说明上一个遍历到的节点就是共同节点的第一个。

需要注意的特殊点有

1. 两个链表中有一个链表是NULL的情况；
2. 两个链表有一个链表的头节点就是共用节点，甚至两个链表的头节点均是公用节点；

对于第一种情况，毋庸置疑return NULL即可，但是对于第二种情况的判断有些麻烦

我们前面提到过，我们是从后往前遍历的，我们使用一个pub_x意思是倒数第pub_x个节点，则当pub_x等于链表的长度时，说明到达头节点了，这样将头节点return回去即可。

我们只需要在每遍历一个节点给pub_x执行++操作即可。

int getlength(struct ListNode* head)
{
    int len = 0;
    while(head!=NULL)
    {
        len++;
        head = head->next;
    }
    return len;
}
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* p1 = pHead1;
    struct ListNode* p2 = pHead2;
    int len1 = getlength(p1);
    int len2 = getlength(p2);
    int pub_x = 1;
    struct ListNode* output = NULL;
    while(1)
    {
        struct ListNode* output1 = pHead1;
        for(int i=0;i<len1-pub_x;i++)
        {
            output1 = output1 -> next;
        }
        struct ListNode* output2 = pHead2;
        for(int i=0;i<len2-pub_x;i++)
        {
            output2 = output2->next;
        }
        if(output1!=NULL&&output2!=NULL)
        {
            if(output1==output2)
            {
                output = output1;
                printf("%d\n", output->val);
            }
            if(output1!=output2||pub_x==len1||pub_x==len2)
            {
                return output;
            }
        }
        if(output1==NULL||output2==NULL)
        {
            return NULL;
        }
        pub_x++;
    }
}