160. 相交链表.md

date created	date modified
2022-09-11, 09:12:39	2022-09-11, 09:12:47

Meta

• alias:
• parent :: [[algo-奇思妙想]]
• siblings ::
• child ::
• refs: https://leetcode.cn/problems/intersection-of-two-linked-lists/

---

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 核心思想：考虑两链表相交的一般情况，由于两个指针距离相交点路程不一样，所以
        // 无法同时到达相交点，可以让两指针走的路程一样，那么相同出发时间、相同速度，若路径
        // 长度相同，则最终会同时到达终点。
        
        // 让 A 指针走完 A 链后走 B 链，让 B 指针走完 B 链后走 A 链
        // A 和 B 所走的路程长度均为：a(a1-a2) + c(c1-c3) + b(b1-b3)
        // 若两链表不相交，按上述逻辑，最终同时到达对方链表的末位，null 节点

        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a.next;
            b = b.next;
            if (a == b) break;
            if (a == null) a = headB;
            if (b == null) b = headA;
        }
        return a;
    }
}