题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ #include <unordered_set> class Solution { public: // 双指针遍历,遍历完自己的链表就去遍历另一个链表,直到两个指针相遇 ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode* head1 = pHead1; ListNode* head2 = pHead2; while (pHead1 != pHead2) { if (pHead1==nullptr) { pHead1 = head1; } else { pHead1 = pHead1->next; } if(pHead2 == nullptr){ pHead2 = head2; } else { pHead2 = pHead2->next; } } return pHead1; } // 哈希表 空间复杂度O(n) // ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { // unordered_set<ListNode*> hax; // while (pHead1) { // hax.insert(pHead1); // pHead1 = pHead1->next; // } // while (hax.count(pHead2)==0 && pHead2) { // pHead2 = pHead2->next; // } // return pHead2; // } };
两个方法
一:双指针法. 使用两个指针同样的速度遍历两个链表,并且当遍历完自己的链表后就去遍历另一个链表,直到两个指针相遇。
二:哈希表法. 首先遍历其中一个链表,并把节点指针保存在哈希表中,当遍历另一个链表时,判断当前节点指针是否已经存在于上述哈希表中,如果是则输出此节点。