[剑指Offer]52-两个链表的第一个公共节点

题目链接

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意

输入两个链表，找出它们的第一个公共结点。

题解

有公共节点的链表一定是Y字形，而不是X字形。

• 法一:时间复杂度O(m+n)，空间复杂度O(m+n)
  从后到前的最后一个公共节点即是所求节点，但遍历链表要从前往后，情景比较像栈。
  所以用两个栈分别装两个链表的节点，一起出栈的最后一个公共节点即是所求节点。
  采用了用空间换时间的思想。
• 法二:时间复杂度O(m+n),不需要辅助空间
  采用栈，实际上是想同时遍历到两个链表尾节点。
  所以可以遍历链表两次，第一次获得两个链表的长度，
  然后将指向较长链表的指针先往后移长度差值个节点，然后同时遍历两个链表，即可找到第一个公共节点。

法二代码

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        //遍历得到两个链表长度
        int len1=0;
        int len2=0;
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        while(p1){
            ++len1;
            p1=p1->next;
        }
        while (p2) {
            ++len2;
            p2=p2->next;
        }
        
        //较长的链表先走dif个
        p1=pHead1;
        p2=pHead2;
        int dif=abs(len1-len2);
        if(len1>=len2){
            while(dif--){
                p1=p1->next;
            }
        }
        else{
            while(dif--){
                p2=p2->next;
            }
        }
        
        //找第一个公共节点
        while(p1){
            if(p1==p2){
                return p1;
            }
            else{
                p1=p1->next;
                p2=p2->next;
            }
        }
        
        return nullptr;
    }
};