题目描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。

例如：

输入：headA = [4,1,8,4,5], headB = [5,6,1,8,4,5]
输出：Intersected at '8'

解题思路

我们要找到两个单链表相交的起始节点，这样的节点从它开始，链表A和链表B共享相同的节点。从链表的末尾开始相同的节点会一直持续，直到到达相交节点。

双指针遍历

双指针法可以有效地解决这个问题：

1. 初始化两个指针：指针 pA 指向 headA，指针 pB 指向 headB。
2. 遍历链表：依次遍历 A 链表和 B 链表，在遍历到末尾（即 nullptr）时，切换到另一个链表继续遍历。具体来说：
   • 如果 pA 到达 nullptr，则让 pA 指向 headB 重新开始遍历链表B。
   • 同样，如果 pB 到达 nullptr，则让 pB 指向 headA 重新开始遍历链表A。
3. 找到相交节点：继续上述过程，直到 pA 和 pB 相遇，这个相遇点即为相交节点。如果两个指针没有相遇且都遍历完了两个链表，则返回 nullptr 表示没有相交节点。

原理解释

通过将两个指针从链表A和链表B切换，使它们走到相同的距离。如果存在相交节点，两个指针最终会在相交节点相遇。这个方法确保两个指针走过相同的节点总数，有效地消除了长度差异。

算法实现

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) {ListNode*curA=headA;ListNode*curB=headB;int lenA=0,lenB=0;while(curA!=NULL){lenA++;curA=curA->next;}while(curB!=NULL){lenB++;curB=curB->next;}curA=headA;curB=headB;if(lenA<lenB){swap(lenA,lenB);swap(curA,curB);}int nap=lenA-lenB;while(nap--){curA=curA->next;}while(curA!=NULL){if(curA==curB){return curA;}curA=curA->next;curB=curB->next;}return NULL;}
};

复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。两个指针各自遍历两个链表，总共走了m + n的节点数。
• 空间复杂度：O(1)，只使用了常数额外空间，没有使用额外的数据结构。

总结

通过使用双指针遍历的方法，我们可以在不改变链表结构和节点值的情况下，找到两个单链表的相交节点。这种方法高效、简单，非常适合解决链表相交问题。

希望这篇文章能帮助你更好地理解和解决链表相交的问题。如果有任何问题，欢迎随时讨论与交流。