剑指offer 面试题52. 两个链表的第一个公共节点

这题之前leetcode做过，权当复习

首先这题没说是否一定有公共节点，如果代码可能因为这一点造成死循环的，需要提前验证所给两个链表是否有公共节点。

方法1：对于每一个list1的节点，遍历list2查找有无相同节点，O(MN)

方法2：用两个栈分别存储两个链表的所有节点，然后比较二者栈顶（如果有公共节点，那么二者栈顶应该相同）。直到找到最后一对相同的栈顶，即为所求。O(M+N)时间

方法3：用一个set存list2的节点，遍历list1找第一个匹配的，O(N)时间O(N)空间

方法4：分别遍历两个链表计算各自长度L1，L2 长度长的链表先走(L1-L2)，之后一起走，O(N)时间

方法5：数学方法，p1，p2分别从各自链表头部出发，如果p1到达末尾，将其转接到pHead2；如果p2到达末尾，将其转接到pHead1。p1、p2相遇时就是第一个公共节点。这个方法的正确性画图易证，O(N)时间

/*

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==nullptr or pHead2==nullptr){return nullptr;}

        auto p1=pHead1,p2=pHead2;

        while(p1->next){p1=p1->next;}

        while(p2->next){p2=p2->next;}

        if(p1!=p2){return nullptr;}//两个链表的尾节点都不一样，肯定没有公共节点

        p1=pHead1,p2=pHead2;

        while(p1!=p2){

            p1=p1->next;

            if(p1==nullptr){p1=pHead2;}

            p2=p2->next;

            if(p2==nullptr){p2=pHead1;}

        }

        return p1;

    }

};