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

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

```struct ListNode { int value; ListNode* next; }

* * *

### 分析

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

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

代码如下：

```ListNode* FindFirstCommenNode(ListNode* head1,ListNode* head2)
{
    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;
        }
    }
}

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

代码如下：

ListNode* FindFirstCommenNode(ListNode* head1,ListNode* head2) { 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上：点我前往