力扣 – 劍指 Offer 52. 兩個鏈表的第一個公共節點
- 2021 年 11 月 20 日
- 筆記
- 雙指針, 哈希表, 差值法, 棧, 演算法與題解, 鏈表
題目
劍指 Offer 52. 兩個鏈表的第一個公共節點
思路1(棧)
- 若兩個鏈表相遇，則從它開始相遇的地方到鏈表末尾應該都是相同的，那麼我們可以將兩個鏈表分別放入兩個棧中，然後依次循環比較兩個棧頂的節點，同時用
pre記錄上一個節點，直到當前兩個棧頂節點不相等，那麼pre節點就是他們開始相遇的地方
程式碼
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
LinkedList<ListNode> stack1 = new LinkedList<>();
LinkedList<ListNode> stack2 = new LinkedList<>();
// 使用兩個棧分別存儲兩個鏈表的元素
while (headA != null) {
stack1.push(headA);
headA = headA.next;
}
while (headB != null) {
stack2.push(headB);
headB = headB.next;
}
// 若兩個鏈表存在相同的節點，則兩個棧pop出來的節點應該是一樣的
// 如果pop出來的不一樣，說明上一個pop出來相同節點才是相遇開始的節點
// 因此我們需要pre來記錄上一個相同的節點，初始值要為null，如果沒有相遇，那麼會直接返回null
ListNode pre = null;
while (!stack1.isEmpty() && !stack2.isEmpty()) {
ListNode p1 = stack1.pop();
ListNode p2 = stack2.pop();
if (p1 != p2) {
break;
}
// 如果沒有相遇，就不會執行這條語句，因此此時pre為 null，返回的值也是 null
pre = p1;
}
// 返回結果
return pre;
}
}
複雜度分析
- 時間複雜度：\(O(N+M)\)
- 空間複雜度：\(O(N+M)\)
思路2（差值法）
- 先分別計算兩個鏈表的長度記為
lengthA和lengthB，得到他們的差值n，讓長的那個鏈表先走n步，然後兩個鏈表再一起走，第一個相等的地方，則是鏈表開始相遇的地方
程式碼
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA = 0;
int lengthB = 0;
ListNode pA = headA;
ListNode pB = headB;
// 先獲取兩個鏈表的長度
while (pA != null) {
pA = pA.next;
lengthA++;
}
while (pB != null) {
pB = pB.next;
lengthB++;
}
// 計算鏈表長度差n，將長的鏈表先走n步
int n = lengthA > lengthB ? lengthA - lengthB : lengthB - lengthA;
while (lengthA > lengthB && n > 0) {
headA = headA.next;
n--;
}
while (lengthB > lengthA && n > 0) {
headB = headB.next;
n--;
}
// 然後兩個鏈表才開始同時一起走
// 知道兩個節點相等 或者 都為null的時候結束循環
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
}
複雜度分析
- 時間複雜度：\(O(N+M)\)
- 空間複雜度：\(O(1)\)
思路3（雙指針）
- 使用兩個指針
pA和pB分別指向兩個鏈表，然後同時前進，如果到了鏈表末尾，就跳到另一條鏈表的頭節點（要保證不會再跳回來，否則導致死循環）
- 在這過程中，要判斷節點是否相等，第一次相等的地方就是相交的地方，如果沒有那就返回
null
- 在
while中的判斷條件要為當前兩個節點是否相等，因為不這樣的話，如果不存在相交的節點，那麼循環就會一直重複下去；如果判斷條件為當前兩個節點是否相等的話，如果沒有相交節點也不會一直循環下去，因為兩個指針遍歷的長度都為兩個鏈表長度之和，所以最後都會指向null，此時都為null相等，跳出循環
程式碼
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
// 判斷是否相等，遇到相同節點，結束循環；如果鏈表中沒有相同節點，那麼跳出循環的條件是他們都為 null 的時候
while (pA != pB) {
// 判斷的要為當前節點
// 如果判斷的是next節點，那麼到時候就會導致pA、pB永遠不會是null
if (pA == null) {
pA = headB;
} else {
pA = pA.next;
}
if (pB == null) {
pB = headA;
} else {
pB = pB.next;
}
}
return pA;
}
}
複雜度分析
- 時間複雜度：\(O(N)\)
- 空間複雜度：\(O(1)\)
思路4（哈希表）
- 先選擇其中一個鏈表，將其節點全部加入到哈希表中，然後再開始遍歷另一個鏈表，同時也加入到哈希表中
- 如果加入的節點和哈希表衝突了，那麼這個節點就是交點
程式碼
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> set = new HashSet<>();
// 遍歷一次，將鏈表A里的所有節點添加到set中
while (headA != null) {
set.add(headA);
headA = headA.next;
}
// 再遍歷一次鏈表B，同時將鏈表的節點添加到set中，如果添加失敗返回false，那麼說明找到相同的那個節點了，直接返回該節點
while (headB != null) {
if (!set.add(headB)) {
return headB;
}
headB = headB.next;
}
// 如果遍歷鏈表B的時候都沒有找到，說明不存在相同的節點，就返回 null
return null;
}
}
複雜度分析
- 時間複雜度：\(O(N+M)\)
- 空間複雜度：\(O(N)\)，哈希表所佔空間大小
