1. 题目

描述
输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

示例1

  1. 输入：复制
  2. {1,2,3},{4,5},{6,7}
  3. 返回值：复制
  4. {6,7}
  5. 说明：
  6. 第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分 这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

示例2

输入：复制
{1},{2,3},{}
返回值：复制
{}
说明：
2个链表没有公共节点 ,返回null，后台打印{}

2. 解题思路

  1. 如果两个链表存在公共结点，那么它们从公共结点开始一直到链表的结尾都是一样的，因此我们只需要从链表的结尾开始，往前搜索，找到最后一个相同的结点即可。但是题目给出的单向链表，我们只能从前向后搜索，这时，我们就可以借助栈来完成。先把两个链表依次装到两个栈中，然后比较两个栈的栈顶结点是否相同，如果相同则出栈，如果不同，那最后相同的结点就是我们要的返回值。

    /*
struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
         val(x), next(NULL) {
 }
};*/
class Solution {
public:
 ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
     /*
         如果两个链表存在公共结点，那么它们从公共结点开始一直到链表的结尾都是一样的，
         因此我们只需要从链表的结尾开始，往前搜索，找到最后一个相同的结点即可。
         但是题目给出的单向链表，我们只能从前向后搜索，这时，我们就可以借助栈来完成。
         先把两个链表依次装到两个栈中，然后比较两个栈的栈顶结点是否相同，
         如果相同则出栈，如果不同，那最后相同的结点就是我们要的返回值。
     */
     ListNode* node1 = pHead1;
     ListNode* node2 = pHead2;
     // 记录结果
     ListNode* result = nullptr;
     stack<ListNode*> tmpStack1;
     stack<ListNode*> tmpStack2;

     while(node1){
         tmpStack1.push(node1);
         node1 = node1->next;
     }
     while(node2){
         tmpStack2.push(node2);
         node2 = node2->next;
     }

     while (!tmpStack1.empty() && !tmpStack2.empty()) {
         if (tmpStack1.top()->val == tmpStack2.top()->val) {
             result = tmpStack1.top();
             tmpStack1.pop();
             tmpStack2.pop();
         }
         else {
             // 当前节点不一样，返回下一个节点
             return tmpStack1.top()->next;
         }
     }

     return result;
 }
};

  1. 先找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走，直到找到第一个公共结点。

    /*
struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
         val(x), next(NULL) {
 }
};*/
class Solution {
public:
 ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
     /*
         先找出2个链表的长度，然后让长的先走两个链表的长度差，
         然后再一起走，直到找到第一个公共结点。
     */
     ListNode* node1 = pHead1;
     ListNode* node2 = pHead2;
     int len1 = 0;
     int len2 = 0;

     while (node1) {
         len1++;
         node1 = node1->next;
     }
     while (node2) {
         len2++;
         node2 = node2->next;
     }

     if (len1 == 0 || len2 == 0) {
         return nullptr;
     }

     // 长的先走，走的距离：长的-短的
     if (len1 > len2){
         for (int i = 0; i < len1 - len2; i++)
             pHead1 = pHead1->next;

         while (pHead1) {
             if (pHead1->val == pHead2->val)
                 return pHead1;
             else {
                 pHead1 = pHead1->next;
                 pHead2 = pHead2->next;
             }
         }
     }
     else {
         for (int i = 0; i < len2 - len1; i++)
             pHead2 = pHead2->next;

         while (pHead1) {
             if (pHead1->val == pHead2->val)
                 return pHead1;
             else {
                 pHead1 = pHead1->next;
                 pHead2 = pHead2->next;
             }
         }
     }

     return nullptr;
 }
};