160. 相交链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 351 阅读时长 ≈ 1 分钟

考点

  • 链表的相交

题解

1
2
3
4
5
6
7
8
9
10
11
class Solution {
	public:
		ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
			ListNode *curA = headA, *curB = headB;
			while (curA != curB) {
				curA = curA == nullptr ? headB : curA->next;
				curB = curB == nullptr ? headA : curB->next;
			}
			return curA;
		}
};

思路

链表的相交问题需要用到双指针

设链表A的节点为{a1, a2, c1, c2}，链表B的节点为{b1, b2, b3, c1, c2}；两个链表相交于节点c1，自节点c1起为相交公共部分

假设游标指针curA和curB同时出发，并最终相交于节点c1；观察路径轨迹，可以发现有以下恒等式： \[ \underset{curA\text{遍历链表}A}{\underbrace{a1+a2+c1+c2}}+\underset{curA\text{遍历}B\text{部分}}{\underbrace{b1+b2+b3}}+c1=\underset{curB\text{遍历链表}B}{\underbrace{b1+b2+b3+c1+c2}}+\underset{curB\text{遍历}A\text{部分}}{\underbrace{a1+a2}}+c1 \] 故而，若A、B两个链表存在交点，应做如下操作：

  • curA遍历A链表，然后再从B链表头节点继续遍历

  • curB遍历B链表，然后再从A链表头节点继续遍历

  • curA和curB的遍历同步进行；最终会相遇在相交节点

假如不相交呢？最终curA和curB两个指针值也是相等的，均为nullptr

因为curA先遍历了A链表再遍历了B链表，curB先遍历了B链表再遍历了A链表，两个指针又是同时遍历，自然最终结果一样