面试题37:两个链表的第一个公共节点

题目:输入两个链表,找出它们的第一个公共节点。链表节点定义如下:

{
    int value;
    ListNode* next;
}

分析

解法有两种,分别介绍如下:

第一种,先分别在两个链表上遍历一次,统计出两个链表的长度,假设为length1和length2,且length1>length2。然后在较长的链表上先走(length1-length2)步,然后两个同时走,如果遇到相等的,就表示找到了。

代码如下:

{
    if(head1==NULL || head2==NULL)
        return NULL;
    int count1=0,count2=0;
    int i;
    ListNode* cur1=head1,*cur2=head2;
    while(cur1!=NULL)
    {
        count1++;
        cur1=cur1->next;
    }
    while(cur2!=NULL)
    {
        count2++;
        cur2=cur2->next;
    }
    cur1=head1,cur2=head2;
    if(count1>count2)
    {
        for(i=0;i<count1-count2;++i)
        {
            cur1=cur1->next;
        }
    }
    else if(count2>count1)
    {
        for(i=0;i<count2-count1;++i)
        {
            cur2=cur2->next;
        }
    }
    while(cur1!=NULL &amp;&amp; cur2!=NULL)
    {
        if(cur1==cur2)
        {
            return cur1;
        }
        else
        {
            cur1=cur1->next;
            cur2=cur2->next;
        }
    }
}

以上这种方法会将两个链表都遍历两次,有没有办法治遍历一次呢?答案是有的。我们只需要将每个节点的指针都各自放进一个栈中,然后从栈中逐个弹出。若某一次弹出的两个节点不相等,则上一次弹出的就是他们的第一个公共节点。

代码如下:

{
    if(head1==NULL || head2==NULL)
        return NULL;
    stack<ListNode*> s1,s2;
    ListNode* cur1=head1,*cur2=head2;
    while(cur1!=NULL || cur2!=NULL)
    {
        if(cur1!=NULL)
        {
            s1.push(cur1);
            cur1=cur1->next;
        }
        if(cur2!=NULL)
        {
            s2.push(cur2);
            cur2=cur2->next;
        }
    }
    while(!s1.empty() || !s2.empty())
    {
        if(!s1.empty() &amp;&amp; !s2.empty())
        {
            if(s1.top()==s2.top())
            {
                s1.pop();
                s2.pop();
            }
            else
            {
                return s1.top()->next;
            }
        }
        else if(!s1.empty())
        {
            if(s1.top()->next==head2)
            {
                return head2;
            }
            else
            {
                return NULL;
            }
        }
        else if(!s2.empty())
        {
            if(s2.top()->next==head1)
            {
                return head1;
            }
            else
            {
                return NULL;
            }
        }
    }
    if(s1.empty() &amp;&amp; s2.empty())
        return head1;
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")