相交鏈表（浪漫指針相遇法）

走到盡頭見不到你，因而走過你來時的路，等到相遇時才發現，你也走過我來時的路。java

題目

Leetcode 160：找到兩個單鏈表相交的起始節點指針

解法

一種比較巧妙的方式是，分別爲鏈表A和鏈表B設置指針A和指針B，而後開始遍歷鏈表，若是遍歷完當前鏈表，則將指針指向另一個鏈表的頭部繼續遍歷，直至兩個指針相遇。code

若兩個鏈表相交，則指針A和指針B一定在相交結點相遇；若兩個結點不相交，則將會同時到達NULL。leetcode

代碼（JAVA）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

時間複雜度：O(n)get

空間複雜度：O(1)io

若是對您有幫助，記得留個贊喲~class