剑指52：两个链表的第一个公共节点

传送门

nowcoder
leetcode

题目描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

C++ 代码 - nowcoder

/*
    双指针
    第一轮移动使到达链表尾部的节点指向另一个链表的头部（消除了两个链表的长度之差）
    如果两个指针相遇，两个指针等于移动了相同的距离，则返回；
    如果两个指针不相遇，两个指针各自走了两个链表的长度。
    
    时间复杂度：O(n + m)
    空间复杂度：O(1)
*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr || pHead2 == nullptr) return nullptr;

		ListNode *p1 = pHead1, *p2 = pHead2;
		while (p1 != p2) {
			p1 = (p1 == nullptr ? pHead2 : p1->next);
			p2 = (p2 == nullptr ? pHead1 : p2->next);
		}

		return p1;
    }
};

C++ 代码 - leetcode

/*
	双指针
	
	时间复杂度：O(n + m)
	空间复杂度：O(1)
*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;

        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2) {
            p1 = (p1 == nullptr ? headB : p1->next);
            p2 = (p2 == nullptr ? headA : p2->next);
        }

        return p1;
    }
};

/* 
	集合
	
	时间复杂度：O(n + m)
	空间复杂度：O(n)
*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> set;

        ListNode* temp = headA;
        while (temp != nullptr) {
            set.insert(temp);
            temp = temp->next;
        }

        temp = headB;
        while (temp != nullptr) {
            if (set.count(temp)) return temp;
            else temp = temp->next;
        }

        return nullptr;
    }
};