【2024考研】题解9 | #两个链表的第一个公共结点#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1 = pHead1;
		ListNode *p2 = pHead2;
		//不是自己的事就互相甩锅，都甩不掉时，第一个公事就找到了
		while(p1 != p2){
			p1 = p1 ? p1->next : pHead2;
			p2 = p2 ? p2->next : pHead1;
		}
		return p1;
    }
};
/*
算法思想：
该算法使用了双指针的思想。假设两个链表的长度分别为m和n，首先两个指针p1和p2分别指向两个链表的头节点。然后它们同时向后遍历，当其中一个指针p1或p2到达链表的末尾时，将其指向另一个链表的头节点。这样，当两个指针相遇时，即找到了第一个公共节点。如果两个链表没有公共节点，那么最终两个指针都会指向NULL，退出循环。

时间复杂度：
该算法的时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。

空间复杂度：
该算法的空间复杂度为O(1)，只使用了常数级别的额外空间。

总结：
该算法通过双指针的方式来寻找两个链表的公共节点，时间复杂度为O(m+n)，空间复杂度为O(1)。
*/