面试题37.两个链表的第一个公共结点

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

1 struct ListNode
2 {
3      int     m_nKey;
4      ListNode* m_pNext;  
5 }

一共三种方法解答此题目:

方法1:双层遍历链表,复杂度为O(m*n)

方法2:有两个栈存储链表结点模拟从后往前遍历

方法3:先计算出两个链表长度，然后使得较长的链表先走k步与短链表对齐再一起向后比较

这里我们只介绍方法三

我们以链表:

1->2->3->6->7

4->5->6->7为例

1.先计算出链表1长度为5链表2长度为4

2.链表1比链表2长一个结点那么让链表1先走一步到结点2

3.两个链表同时向后遍历并比较遇到相同的结点返回并结束

简单实现如下:

  1 #include <iostream>
  2 using namespace std;
  3 
  4 struct ListNode
  5 {
  6      int     m_nKey;
  7      ListNode* m_pNext;  
  8 };
  9 
 10 void PrintListNode(ListNode* Head)
 11 {
 12     ListNode* Temp=Head;
 13     while(Temp!=NULL)
 14     {
 15         cout<<Temp->m_nKey<<",";
 16         Temp=Temp->m_pNext;
 17     }
 18     cout<<endl;
 19 }
 20 
 21 
 22 ListNode* FindTheFirstSameNode(ListNode*Head1,ListNode* Head2)
 23 {
 24     if(Head1==NULL||Head2==NULL)
 25         return NULL;
 26 
 27     ListNode* TempHead1=Head1;
 28     ListNode* TempHead2=Head2;
 29     
 30     int len1=0;
 31     int len2=0;
 32 
 33     while(TempHead1!=NULL)
 34     {
 35         len1++;
 36         TempHead1=TempHead1->m_pNext;
 37     }
 38     while(TempHead2!=NULL)
 39     {
 40         len2++;
 41         TempHead2=TempHead2->m_pNext;
 42     }
 43 
 44     int k=0;
 45     TempHead1=Head1;
 46     TempHead2=Head2;
 47     if(len1>len2)
 48     {
 49         k=len1-len2;
 50         TempHead1=Head1;
 51         int count=0;
 52         while(count<k)
 53         {
 54             TempHead1=TempHead1->m_pNext;
 55             count++;
 56         }
 57     }
 58     if(len2>len1)
 59     {
 60         k=len2-len1;
 61         TempHead2=Head2;
 62         int count=0;
 63         while(count<k)
 64         {
 65             TempHead2=TempHead2->m_pNext;
 66             count++;
 67         }
 68     }
 69 
 70 
 71     while(TempHead1!=NULL&&TempHead2!=NULL)
 72     {
 73         if(TempHead1->m_nKey==TempHead2->m_nKey)
 74              return TempHead1;
 75         
 76         TempHead1=TempHead1->m_pNext;
 77         TempHead2=TempHead2->m_pNext;
 78     }
 79 
 80     return NULL;
 81 }
 82 
 83 
 84 int main()
 85 {
 86     ListNode *Head1;
 87     Head1=new ListNode();
 88     Head1->m_nKey=1;
 89     Head1->m_pNext=NULL;
 90 
 91     ListNode *Node1=new ListNode();
 92     ListNode *Node2=new ListNode();
 93     ListNode *Node3=new ListNode();
 94     ListNode *Node4=new ListNode();
 95 
 96     Node1->m_nKey=2;
 97     Node1->m_pNext=NULL;
 98     
 99 
100     Node2->m_nKey=3;
101     Node2->m_pNext=NULL;
102 
103     Node3->m_nKey=6;
104     Node3->m_pNext=NULL;
105 
106     Node4->m_nKey=7;
107     Node4->m_pNext=NULL;
108 
109     Head1->m_pNext=Node1;
110     Node1->m_pNext=Node2;
111     Node2->m_pNext=Node3;
112     Node3->m_pNext=Node4;
113     
114     ListNode *Head2=new ListNode();
115     Head2->m_nKey=4;
116     Head2->m_pNext=NULL;
117     
118     ListNode *Node5=new ListNode();
119     Node5->m_nKey=5;
120     Node5->m_pNext=NULL;
121 
122     Head2->m_pNext=Node5;
123 
124 
125     Node5->m_pNext=Node3;
126     cout<<"PrintListNode One: ";
127     PrintListNode(Head1);    
128 
129     cout<<"PrintListNode Two: ";
130     PrintListNode(Head2);    
131 
132     ListNode* FirstNode;
133     FirstNode=FindTheFirstSameNode(Head1,Head2);
134 
135     cout<<"The First SameNode is: "<<FirstNode->m_nKey<<endl;
136     return 0;
137 }

运行截图:

代码中结点的释放读者自行释放即可。