题目描述：

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

 

解题思路：

这道题一开始的题意不太理解，这里的公共结点，实际上指结点指相同，在题目不存在结点值相同的不同结点。

1. 最直接的思路是对链表一的每个结点去和链表二中的结点进行比较，这样的复杂度是O(n^2)。

2. 这里的一个小技巧是，从第一个公共结点后，实际上两个链表的后面结点就是共享的了，同样考虑用空间换时间。利用栈来存每个链表中的结点。由于需要找到第一个公共结点，那么就可以比较两个栈的栈顶元素，相等就同时出栈，继续比较。需要注意的时对于每一次出栈的公共结点都需要保存，这样当两个栈顶元素不同时，之前保存的公共结点就是第一个公共结点了。复杂度降到O(n)。

3. 第三种思路是，不借助辅助空间来进行。首先分别遍历两个链表，记录二者的长度。那么其中存在一个长链表和一个短链表。那么二者的公共部分的长度一定小于等于短链表的长度，因此首先遍历完长链表比短链表多出的部分。再同时遍历两个链表，则相同的结点即为第一个公共结点。

 

代码：

思路二：

1 /* 2 struct ListNode { 3     int val; 4     struct ListNode *next; 5     ListNode(int x) : 6             val(x), next(NULL) { 7     } 8 };*/ 9 class Solution {10 public:11     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {12         if(pHead1==nullptr || pHead2==nullptr)13             return nullptr;14         stack
     
      s1, s2;15         ListNode* p = pHead1;16         while(p!= nullptr)17         {18             s1.push(p);19             p = p->next;20         }21         p = pHead2;22         while(p!=nullptr)23         {24             s2.push(p);25             p = p->next;26         }27         p = s1.top();28         ListNode* p2 = s2.top();29         while(!s1.empty() && !s2.empty())30         {31             if(s1.top()->val==s2.top()->val)32             {33                 p = s1.top();34                 p2 = s2.top();35                 s1.pop();36                 s2.pop();37             }38             else39                 break;40         }41         if(p->val==p2->val)42             return p;43         else44             return nullptr;45     }46 };