题目描述

示例1

输入： {1,2,3},{4,5},{6,7}

返回值： {6,7}

说明： 第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分 这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

题解1:双指针模式

使用两个指针p1,p2，p1从链表1的头节点开始遍历，p2链表2的头节点开始遍历。 p1和p2一起遍历，当p1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同理，如果p2先走完了链表2的尽头，则从链表1的头节点继续遍历.

因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。

有公共节点的时候，p1和p2必会相遇，因为长度一样嘛，速度也一定，必会走到第一个公共的节点

无公共节点的时候，p1和p2则都会走到终点NULL处。

图示为大佬解释图片,非常nice https://uploadfiles.nowcoder.com/files/20210621/908787715_1624289962297/36.gif

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 ==NULL || pHead2 == NULL) return NULL;
        ListNode * p1 = pHead1;
        ListNode * p2 = pHead2;
        while(p1 != p2){
            p1 = p1==NULL ? pHead2:p1->next;//p1没走到NULL,则p1指向下一个节点;走到NULL,p1指向Phead2
            p2 = p2==NULL ? pHead1:p2->next;
        }
        return p1;
    }
};

题解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) {
        if(pHead1 ==NULL || pHead2 == NULL) return NULL;
        题解1:对链表的每个节点进行遍历
        while(pHead1){
            ListNode * temp = pHead2;
            while(temp){
                if(pHead1==temp)
                    return pHead1;
                else{
                    temp = temp->next;
                }
            }
            pHead1 = pHead1->next;
        }
        return NULL;
    }
};