方法一

对于两个链表的问题,首先想到双指针的方法。在这道题中,两个链表长度不一定相等,不能直接使用双指针,我们需要在长链表上先移动一段距离,再进行比较。因为公共部分肯定在链表后面部分,所以不需要担心这一操作导致跳过了第一个公共结点。
示意图如下:
图片说明
具体代码如下:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1=pHead1, *p2=pHead2;
        int len1=0, len2=0;
        //计算两个链表的长度。
        while (p1 != nullptr){
            p1 = p1->next;
            len1++;
        }
        while (p2 != nullptr){
            p2 = p2->next;
            len2++;
        }

        //在长链表上先移动一段距离。
        while (len1!=len2){
            if (len1>len2){
                pHead1 = pHead1->next;
                len1--;
            }
            else{
                pHead2 = pHead2->next;
                len2--;
            }
        }
        //双指针同时开始后移。
        while (pHead1 != pHead2){
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return pHead1;
    }
};

时间复杂度:O(N),我们同时遍历两个链表,其中N为长链表的长度。
空间复杂度:O(1)。

方法二

对于两个链表长度不一定相等的问题,有没有什么办法可以将两个链表长度对齐呢?
假设链表1的长度为a,链表2的长度为b,无论a是否等于b,a+b恒等于b+a。由此,我们可以考虑将两个链表拼接起来,再使用双指针。示意图如下,其中黄色块为公共部分:
图片说明
(1)对于没有公共结点的情况,我们把null视为两个链表各自的结尾,最后求得第一个公共结点为null,输出为空。
(2)在实际物理空间中,并不需要复制链表,只要在指针访问完pHead1之后接着访问pHead2即可实现链表的连接。
具体代码如下:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1=pHead1, *p2=pHead2;
        while (p1 != p2){
            p1 = p1 ? p1->next : pHead2;
            p2 = p2 ? p2->next : pHead1;
        }
        return p1;
    }
};

时间复杂度:O(N+M),对于每一个指针,都遍历了两个链表,其中N和M为两个链表的长度。
空间复杂度:O(1)。