1.題目描述

2.思路

“雙指針切換鏈表頭”
思路一：雙指針+路徑對齊
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}

讓兩個指針走相同的總路徑長度！
設：

鏈表 A 獨有部分長度是 lenA

鏈表 B 獨有部分長度是 lenB

公共部分長度是 lenCommon

那兩個指針會走的路徑：

指針 A：先走 lenA + lenCommon，然后換到 B 頭再走 lenB

指針 B：先走 lenB + lenCommon，然后換到 A 頭再走 lenA

于是總長度都是：lenA + lenB + lenCommon

3.代碼實現

/*** 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) {if(headA==null||headB==null) return null;ListNode PA=headA;ListNode PB=headB;while(PA!=PB){if(PA!=null){PA=PA.next;}else{PA=headB;}if(PB!=null){PB=PB.next;//如果PB列表有元素就直接指向下一個}else{PB=headA;//如果PB已經到末尾了，開始遍歷A列表}}return PB;//這邊返回PA和PB都可以}
}