[160] Intersection of Two Linked Lists 链表相交

[160] Intersection of Two Linked Lists

力扣题目链接

1. 长度对齐法

1.1 思想

相交链表的两个性质：

1. 共享尾部

   如果两个单向链表相交，那么从第一个相交节点开始，到链表末尾的所有节点，都是两条链表完全共享的。它们不可能在此之后再分开。

2. 交点即指针相等

   真正的相交，必须是物理上（内存地址上）的汇合，而不是节点值恰好相等。

   所谓的“交点”，不是指两个节点的 val 值相等，而是指两个链表的指针指向了内存中同一个节点对象。

   因此，在代码中，我们寻找交点的方法是直接比较指针是否相等：if (pointerA == pointerB)。

利用这个性质，我们可以让两个指针分别从两条链表的某个位置出发，保证它们到链表末-尾的距离相等，然后同步前进，找到它们第一次相遇（指针相等）的地方。

1.2 AC代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // --- 1. 计算两个链表的长度 --- ListNode *curA = headA; ListNode *curB = headB; int lenA = 0, lenB = 0; // 遍历链表A，获取其长度 while (curA != nullptr) { lenA++; curA = curA->next; } // 遍历链表B，获取其长度 while (curB != nullptr) { lenB++; curB = curB->next; } // --- 2. 对齐两个链表的起点 --- // 将指针重新移回头节点，准备进行对齐操作 curA = headA; curB = headB; // 通过 swap 保证 curA 指向较长的链表，curB 指向较短的链表 // 这样做可以简化后续代码，无需写 if-else 分支 if (lenB > lenA) { swap(lenA, lenB); swap(curA, curB); } // 计算长度差 int gap = lenA - lenB; // 让较长的链表的指针 curA 先向前移动 gap 步 // 移动后，curA 和 curB 到达链表末尾的距离就相等了 while (gap--) { curA = curA->next; } // --- 3. 同步前进，寻找第一个相交节点 --- while (curA != nullptr) { // 核心判断：比较两个指针是否指向同一个内存地址 // 如果指针相等，说明找到了第一个公共节点 if (curA == curB) { return curA; } curA = curA->next; curB = curB->next; } // 如果循环结束都没有相遇，说明两个链表不相交 return nullptr; }

1.3 时空复杂度

时间复杂度：O(La + Lb)

空间复杂度：O(1)

2.双指针法