160. Intersection of Two Linked Lists
給定兩個單鏈表的頭結點 headA 和 headB，返回兩個鏈表相交的節點。如果兩個鏈表沒有交點，則返回 null。
例如，下面的兩個鏈表在節點 c1 開始相交：
測試用例生成方式保證整個鏈表結構中沒有循環。
注意，在函數返回後，鏈表必須保持其原始結構。
自定義測試：
給定如下輸入（你的程序不會直接獲取這些輸入）：intersectVal：相交節點的值。如果沒有相交節點，則為 0。
listA：第一個鏈表。
listB：第二個鏈表。
skipA：從 listA 的頭開始到達相交節點前需要跳過的節點數。
skipB：從 listB 的頭開始到達相交節點前需要跳過的節點數。
測試程序會基於這些輸入創建鏈表結構，並將兩個頭結點 headA 和 headB 傳遞給你的程序。如果你正確地返回了相交的節點，那麼你的解決方案會被接受。
範例 ：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：相交於 8
解釋：相交節點的值是 8（注意，如果兩個鏈表相交，相交節點的值不會是 0）。
從 A 的頭開始，鏈表讀作 [4,1,8,4,5]。從 B 的頭開始，鏈表讀作 [5,6,1,8,4,5]。在 A 中，有兩個節點在相交節點之前；在 B 中，有三個節點在相交節點之前。注意，相交節點的值不是 1，因為 A 中的第二個節點和 B 中的第三個節點的值都是 1，但它們是不同的節點引用。換句話說，它們指向內存中的兩個不同位置，而 A 中的第三個節點和 B 中的第四個節點的值是 8，它們指向相同的內存位置。
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
# Create two pointers for both lists
pA = headA
pB = headB
# Iterate through the lists
while pA != pB:
# If we reach the end of one list, switch to the beginning of the other list
pA = pA.next if pA else headB
pB = pB.next if pB else headA
# Either they meet at the intersection point, or both become None (end of lists)
return pA
27.05MB, 88ms
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA;
ListNode *pB = headB;
while (pA != pB) {
pA = (pA == nullptr) ? headB : pA->next;
pB = (pB == nullptr) ? headA : pB->next;
}
return pA;
}
};
17.09MB, 40ms
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
if (headA === null || headB === null) return null;
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
return pA;
};
59.36MB, 82ms
