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

题目中的信息：

• 两个链表含有公共节点或没有，有公共节点则返回第一公共节点指针
• 单链表，无循环
• 没有公共节点返回空

举一反三：

学习完本题的思路你可以解决如下题目：

BM4.合并有序链表

BM5.合并k个已排序的链表

BM6.判断链表中是否有环

BM7.链表中环的入口节点

BM8.链表中倒数最后k个节点

BM9.删除链表的倒数第n个节点

BM13.判断一个链表是否为回文结构

BM14.链表的奇偶重排

方法一：双指针长度比较法（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

如果两个链表有公共节点，那么它们后半部分都是相同的，我们要找的也就是后半部分的第一个节点。链表前半部分不同，长度也可能不同，因此同时遍历的话不一定就会同时到达第一个公共节点。

但是，如果我们能够找到长度差：

int n = p1 - p2;

较长的链表指针先走$nn$步：

//假设pHead1更长
for(int i = 0; i < n; i++)
    pHead1 = pHead1.next;

然后两个指针分别走剩余的步数，就会同时到达第一个公共节点。

具体做法：

• step 1：单独的遍历两个链表，得到各自的长度。
• step 2：求得两链表的长度差$nn$，其中较长的链表的指针从头先走$nn$步。
• step 3：两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共节点。

图示：

Java实现代码：

public class Solution {
    //计算链表长度的函数
    public int ListLenth(ListNode pHead){  
        ListNode p = pHead;
        int n = 0;
        while(p != null){
            n++;
            p = p.next;
        }
        return n;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int p1 = ListLenth(pHead1);  
        int p2 = ListLenth(pHead2);
        //当链表1更长时，链表1指针先走p1-p2步
        if(p1 >= p2){  
            int n = p1 - p2;
            for(int i = 0; i < n; i++){
                pHead1 = pHead1.next;
            }
            //两个链表同时移动，直到有公共节点时停下
            while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){ 
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        //反之，则链表2先行p2-p1步
        else{  
            int n = p2 - p1;
            for(int i = 0; i < n; i++){
                pHead2 = pHead2.next;
            }
            //两个链表同时移动，直到有公共节点时停下
            while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        return pHead1;
    }
}

C++实现代码：

class Solution {
public:
    //计算链表长度的函数
    int ListLenth( ListNode* pHead){  
        ListNode* p = pHead;
        int n = 0;
        while(p != NULL){
            n++;
            p = p->next;
        }
        return n;
    }
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int p1 = ListLenth(pHead1);  
        int p2 = ListLenth(pHead2);
        //当链表1更长时，链表1指针先走p1-p2步
        if(p1 >= p2){ 
            int n = p1 - p2;
            for(int i = 0; i < n; i++){
                pHead1 = pHead1->next;
            }
            //两个链表同时移动，直到有公共节点时停下
            while((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)){ 
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
        }
        //反之，则链表2先行p2-p1步
        else{ 
            int n = p2 - p1;
            for(int i = 0; i < n; i++){
                pHead2 = pHead2->next;
            }
            //两个链表同时移动，直到有公共节点时停下
            while((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)){
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
        }
        return pHead1;
    }
};

Python代码实现：

class Solution:
    #计算链表长度的函数
    def ListLenth(self, pHead): 
        p = pHead
        n = 0
        while p:
            n += 1
            p = p.next
        return n
    
    def FindFirstCommonNode(self , pHead1 , pHead2 ):    
        p1 = self.ListLenth(pHead1)
        p2 = self.ListLenth(pHead2)
        #当链表1更长时，链表1指针先走p1-p2步
        if p1 >= p2: 
            n = p1 - p2
            for i in range(n):
                pHead1 = pHead1.next
            #两个链表同时移动，直到有公共节点时停下
            while pHead1 and pHead2 and pHead1 != pHead2:
                pHead1 = pHead1.next
                pHead2 = pHead2.next
        #反之，则链表2先行p2-p1步
        else: 
            n = p2 - p1
            for i in range(n):
                pHead2 = pHead2.next
            #两个链表同时移动，直到有公共节点时停下
            while pHead1 and pHead2 and pHead1 != pHead2:
                pHead1 = pHead1.next
                pHead2 = pHead2.next
        return pHead1

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中n为两链表较长者的长度，虽是多次循环，但都为单循环，取最大值即为$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，常数级指针，无额外辅助空间使用

方法二：双指针连接法（扩展思路）

思路：

由上种方法长度差的思路，不同于上述一个指针先走另一个指针后走，仅需将两个链表连在一起，两个指针同步走。

p1 = p1 == NULL ? pHead2 : p1->next;   
p2 = p2 == NULL ? pHead1 : p2->next;

易知将两个链表连在一起长度都相等，对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分因都走了两个链表，因此也是相同的，所以绕了一圈，第一个相同的节点便是第一个公共节点。

具体做法：

• step 1：判断链表情况，其中有一个为空，则不能有公共节点，返回null。
• step 2：两个链表都从表头开始同步依次遍历。
• step 3：不需要物理上将两个链表连在一起，仅需指针在一个链表的尾部时直接跳到另一个链表的头部。
• step 4：根据上述说法，第一个相同的节点便是第一个公共节点。

图示：

Java实现代码：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //其中有一个为空，则不能有公共节点，返回null
        if(pHead1 == null || pHead2 == null) 
            return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        //相当于遍历两次两个链表所有值
        while(p1 != p2){ 
            p1 = p1 == null ? pHead2 : p1.next;   
            p2 = p2 == null ? pHead1 : p2.next;
        }
        return p1;
    }
}

C++实现代码：

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        //其中有一个为空，则不能有公共节点，返回NULL
        if(!pHead1 || !pHead2) 
            return NULL;
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        //相当于遍历两次两个链表所有值
        while(p1 != p2){
            p1 = p1 == NULL ? pHead2 : p1->next;   
            p2 = p2 == NULL ? pHead1 : p2->next;
        }
        return p1;
    }
};

Python代码实现：

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
         #其中有一个为空，则不能有公共节点，返回NULL
        if not pHead1 and not pHead2:
            return None
        p1 = pHead1
        p2 = pHead2
        #相当于遍历两次两个链表所有值
        while p1 != p2: 
            p1 = pHead2 if p1 == None else p1.next
            p2 = pHead1 if p2 == None else p2.next
        return p1

复杂度分析：

• 时间复杂度：$O(n+m)O(n+m)$，其中$mm$与$nn$分别为两链表的长度，因一次遍历两链表，所以为$O(n+m)O(n+m)$，也可以看成是$O(n)O(n)$级别的
• 空间复杂度：$O(1)O(1)$，常数级指针，无额外辅助空间使用