地址 https://www.acwing.com/problem/content/description/62/
输入两个链表，找出它们的第一个公共结点。
当不存在公共节点时，返回空节点。
样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
解法1
由于肯定两个链表头有交集
那么每次移动两个链表头一步，如果移到链表尾则跳转到另一个链表表头继续移动。
最后相交的位置就是第一个公共节点
class Solution { public: ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) { auto p = headA,q = headB; while(q != p ){ if( q) q = q -> next; else q = headA; if(p ) p = p -> next; else p = headB; } return p ; } };
解法2 使用哈希表记录节点 每次移动进行查询 第一个重合的就是公共节点
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) { ListNode* p = headA; set<ListNode*> sp; while(p != NULL){ sp.insert(p); p = p->next; } p= headB; while(p != NULL){ if(sp.count(p) != 0) return p; p = p->next; } return NULL; } };