《剑指Offer》-52-两个链表的第一个公共节点

Yao's Blog / 2023-09-05 / 原文

书上给出的第一个方法是用两个栈，将两个链表的节点依次入栈，然后出栈就相当于从后往前遍历了，这样只需要找到最后一个相同的链表节点
同样应该也可以使用内存栈，也就是递归来实现这一过程

第二种思路不需要额外的空间，而是先分别遍历两个链表得到链表的长度，然后让较长的链表指针将差值走掉，最后就可以同步遍历，第一个相同的节点就是目标

	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {

		ListNode* traverse1 = headA, * traverse2 = headB;
		int len1 = 0, len2 = 0;
		while (traverse1) {
			traverse1 = traverse1->next;
			len1++;
		}

		while (traverse2) {
			traverse2 = traverse2->next;
			len2++;
		}

		// 我需要知道哪一个更长，长多少
		if (len1 > len2) {
			traverse1 = headA;
			traverse2 = headB;
		}
		else {
			traverse1 = headB;
			traverse2 = headA;
		}

		for (int i = 0; i < abs(len1 - len2); i++) {
			traverse1 = traverse1->next;
		}

		while (traverse1 != traverse2) {
			traverse1 = traverse1->next;
			traverse2 = traverse2->next;
		}
		return traverse1;
	}

第三种思路的核心思想和二一样，基于差值，但是更巧妙、代码量也更少，不需要知道差值是多少也不需要知道长度

用两个指针分别依次去遍历A，B和B，A，这两个链表加起来的长度一定是相等的，第一次两个链表遍历完成后两个交换链表遍历的指针就自动形成了长度的差值

	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {

		if (!headA || !headB) return nullptr;

		ListNode* traverse1 = headA, *traverse2 = headB;
		while (traverse1 != traverse2) {
			traverse1 = traverse1 ? traverse1->next : headB;
			traverse2 = traverse2 ? traverse2->next : headA;
		}
		return traverse1;
	}