在这篇博客中，请允许我分享一下力扣上的算法题目：“两个链表的交点”，记录一下上面的一个有效的解法。该问题的目标是找到两个单链表的交点节点，若无交点则返回NULL。
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。如图所示，两个链表在节点 c1 开始相交：
解题思路
我们可以使用双指针技巧来解决这个问题。我们定义两个指针pa和pb，分别指向两个链表的头节点。在遍历过程中，当某个指针到达链表末尾时，将其指向另一个链表的头部。这样，当两个指针同时遍历两个链表时，它们最终会相遇在交点或同时到达NULL。
详细步骤：
- 初始化两个指针
pa和pb，分别指向headA和headB。 - 逐节点比较
pa和pb，如果它们相等，则找到相交点。 - 如果某个指针遍历到链表末尾，将它指向另一个链表的头部。这样，当两个指针到达相交点时，它们经过的距离相同。
- 如果两个指针都遍历完且没有相交，最终它们会同时到达
NULL，返回NULL表示不相交。
代码实现
以下是实现这一思路的代码：
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB)return NULL;ListNode *pa = headA, *pb = headB;while(pa != pb) {pa = (pa == NULL) ? headB : pa->next;pb = (pb == NULL) ? headA : pb->next;}return pa;}
};
复杂度分析
- 时间复杂度：O(m + n)，其中
m和n分别是两个链表的长度。通过双指针，我们保证每个链表最多遍历两次。 - 空间复杂度：O(1)，只使用了常量空间。
总结
通过这个双指针的方法，我们能够高效地找到链表的交点，避免了使用额外的空间和复杂的哈希表。希望这篇文章能帮助你更好地理解这个经典问题！
