剑指offer编程题—两个链表的第一个公共结点

题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路
典型的用空间换时间做法：
同时遍历两条链表，并将两条链表中访问过的结点存到同一个set容器中，因为set容器中不存在重复结点，当在set中能检索到当前访问结点时，说明该结点就是两条链表的公共结点，在遍历短链表的时候被存到set中了。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
typedef ListNode* node;
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        set<node> st;
        node p=pHead1;
        node q=pHead2;
        while(p || q){
            if(p){
                if(st.find(p)==st.end()) st.insert(p),p=p->next;
                else return p;
            }
            if(q){
                if(st.find(q)==st.end()) st.insert(q),q=q->next;
                else return q;
            }
        }
        return NULL;
    }
};

思路2
同思路1差不多，这里也是先遍历两个链表，但是这里用map标记访问过的结点。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
typedef ListNode* node;
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        map<node,bool> mp;
        node p=pHead1;
        node q=pHead2;
        while(p || q){
            if(p){
                if(mp[p]==true) return p;
                else mp[p]=true, p=p->next;
            }
            if(q){
                if(mp[q]==true) return q;
                else mp[q]=true, q=q->next;
            }
        }
        return NULL;
    }
};

思路3
不需要额外的辅助空间。考虑如下情况：
链表1：a->b->c->d->e->3->4->null
链表2：1->2->3->4->null
第一个公共结点：3
公共尾部：3->4->null
初始化两个指针p、q分别指向链表1和链表2的头部，当两个指针遍历到各自链表的尾部时，改变指针指向，使其指向另一条链表的头部，继续遍历，最终两个指针遍历结点的顺序如下：
指针p：a->b->c->d->e->3->4->null->1->2->3->4->null
指针q：1->2->3->4->null->a->b->c->d->e->3->4->null
很明显，如果链表1和链表2有公共结点，那么两个指针肯定会相遇，如果没有公共结点，则两个指针最后都指向null结点，还是相遇了。
时间复杂度：O(n+m)

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
typedef ListNode* node;
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        node p=pHead1;
        node q=pHead2;
        while(p != q){
            p= (p==NULL? pHead2:p->next); //修改指针p指向重新指向另一条链表
            q= (q==NULL? pHead1:q->next);//修改指针q指向重新指向另一条链表
        }
        return p;
    }
};