剑指offer：两个链表的第一个公共结点

题目描述：

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

解题思路：

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

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<ListNode*>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             else
39                 break;
40         }
41         if(p->val==p2->val)
42             return p;
43         else
44             return nullptr;
45     }
46 };