##題目描述 輸入兩個鏈表，找出它們的第一個公共結點，（注意因為傳入資料是鏈表，所以錯誤測驗資料的提示是用其他方式顯示的，保證傳入資料是正確的）
思路
快慢指標，鏈表長度不同時抵消掉多余的長度，
若鏈表長度不同，則一定時在長鏈表的鏈尾相遇，
時間復雜度O(n)，空間復雜度O(1)，
代碼
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1 != p2) {
// 判斷的位置和處理比較關鍵，整個回圈程序兩個指標的間隔并不是全程不變的，
p1 = p1 == null ? pHead2 : p1.next;
p2 = p2 == null ? pHead1 : p2.next;
}
return p1;
}
}
筆記
鏈表長度不同時，會有兩次指標換鏈，每次換鏈時會導致正在換鏈的指標慢一步，各換鏈一次則步數抵消，且相遇時是在短鏈表的鏈首，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83478.html
標籤：其他
上一篇：CF1304D Shortest and Longest LIS
下一篇：數字在排序陣列中出現的次數