?題目描述
難度：簡單
示例
思路
使用雙指針
使用指針分別指向兩個不同的鏈表進行比較
解題方法
1.首先進行非空判斷
2.初始化指針分別指向兩個鏈表
3.遍歷鏈表
while (pA != pB)：
當
pA和pB不相等時，繼續循環。如果pA和pB相等，說明找到了相交的節點，或者兩個鏈表不相交，pA和pB都為null。
pA = pA == null ? headB : pA.next：
如果
pA為null，說明已經遍歷完鏈表A，接下來從鏈表B的頭節點開始繼續遍歷。如果
pA不為null，則移動到鏈表A的下一個節點。
pB = pB == null ? headA : pB.next：
如果
pB為null，說明已經遍歷完鏈表B，接下來從鏈表A的頭節點開始繼續遍歷。如果
pB不為null，則移動到鏈表B的下一個節點。
4.return pA返回結果
為什么有效
假設鏈表
A的長度為L1，鏈表B的長度為L2，相交部分的長度為C，不相交部分的長度分別為L1 - C和L2 - C。
總移動距離：
pA的總移動距離為L1 + L2。
pB的總移動距離為L2 + L1。兩個指針的總移動距離相同，都是
L1 + L2。相遇點：
如果兩個鏈表有交點，
pA和pB最終會在交點處相遇。如果兩個鏈表沒有交點，
pA和pB最終都會遍歷完兩個鏈表，同時變為null，退出循環。
java代碼
力扣官方題解+個人注解：
public class Solution {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)
空間復雜度
只使用了額外的兩個指針，所以空間復雜度為O(1)
)
)
)
