Leetcode 分類刷題 —— 鏈表類（Linked List）

1、題目

Leetcode 160. Intersection of Two Linked Lists

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回 null 。
題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

2、思路

求兩個(gè)鏈表的相交節(jié)點(diǎn)，首先要讓兩個(gè)鏈表從同距離末尾同等距離的位置開始遍歷，消除兩個(gè)鏈表的長度差可以采用鏈表合并。
pA走過的路徑為：A鏈+B鏈
pB走過的路徑為：B鏈+A鏈
pA、pB走過的長度相同，都是A鏈和B鏈的長度之和，相當(dāng)于將兩條鏈從尾端對齊，如果相交，則會提前在相交點(diǎn)相遇，如果沒有相交點(diǎn)，則會在最后相遇。
注意不是判斷結(jié)點(diǎn)的值相等，而是要判斷結(jié)點(diǎn)本身是否相等，結(jié)點(diǎn)相等意味著結(jié)點(diǎn)值和結(jié)點(diǎn)地址都得相等才行。

3、Java 代碼

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定義兩個(gè)指針, 第一輪讓兩個(gè)到達(dá)末尾的節(jié)點(diǎn)指向另一個(gè)鏈表的頭部, 最后如果相遇則為交點(diǎn)(在第一輪移動(dòng)中恰好抹除了長度差)
        兩個(gè)指針等于移動(dòng)了相同的距離, 有交點(diǎn)就返回, 無交點(diǎn)就是各走了兩條指針的長度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在這里第一輪體現(xiàn)在pA和pB第一次到達(dá)尾部會移向另一鏈表的表頭, 而第二輪體現(xiàn)在如果pA或pB相交就返回交點(diǎn), 不相交最后就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}