当前位置： 面试刷题>> 两个链表的交叉 (经典算法题500道)
### 题目描述补充
给定两个单向链表 `headA` 和 `headB`，这两个链表在某一节点处相交，相交之后的节点值都相同，返回相交点的节点。如果两个链表不相交，则返回 `null`。
注意：
1. 如果两个链表没有交点，则它们仍然是独立的，不会互相引用。
2. 链表中的节点值可能重复。
3. 当链表 `A` 和链表 `B` 相交时，我们假设在交点之前的节点都是独立的，且不会存在循环。
### 示例
假设链表 A 为 `1 -> 2 -> 3 -> 4 -> 5`，链表 B 为 `6 -> 7 -> 4 -> 5`，则相交点是 `4 -> 5`。
### 解题思路
为了找到相交点，我们可以使用双指针法。首先，我们让两个指针分别遍历两个链表，当到达链表末尾时，将指针移向另一个链表的头部继续遍历。由于两个链表在相交点之后是共享的，所以当两个指针都遍历完它们各自的链表并继续遍历对方链表时，它们会在相交点相遇。
### PHP 示例代码
```php
val = $val;
$this->next = $next;
}
}
function getIntersectionNode($headA, $headB) {
$pA = $headA;
$pB = $headB;
while ($pA !== $pB) {
$pA = $pA ? $pA->next : $headB;
$pB = $pB ? $pB->next : $headA;
}
return $pA;
}
// 示例用法
// 假设构建了两个链表并使其相交
// ...
// 调用函数并输出结果
// $intersectionNode = getIntersectionNode($headA, $headB);
// if ($intersectionNode) {
// echo "相交节点的值为: " . $intersectionNode->val;
// } else {
// echo "链表不相交";
// }
?>
```
### Python 示例代码
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def getIntersectionNode(headA, headB):
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA
# 示例用法
# 假设构建了两个链表并使其相交
# ...
# intersection_node = getIntersectionNode(headA, headB)
# if intersection_node:
# print("相交节点的值为:", intersection_node.val)
# else:
# print("链表不相交")
```
### JavaScript 示例代码
```javascript
function ListNode(val) {
this.val = val;
this.next = null;
}
function getIntersectionNode(headA, headB) {
let pA = headA, pB = headB;
while (pA !== pB) {
pA = pA ? pA.next : headB;
pB = pB ? pB.next : headA;
}
return pA;
}
// 示例用法
// 假设构建了两个链表并使其相交
// ...
// let intersectionNode = getIntersectionNode(headA, headB);
// if (intersectionNode) {
// console.log("相交节点的值为:", intersectionNode.val);
// } else {
// console.log("链表不相交");
// }
```
码小课网站中有更多关于链表、算法和数据结构等相关内容的分享，欢迎大家学习交流。