题目描述
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
图示两个链表在节点 c1 开始相交：
A: a1 → a2 ↘ c1 → c2 → c3 ↗
B: b1 → b2 → b3
注意：
- 题目数据保证整个链式结构中不存在环
- 函数返回结果后，链表必须保持其原始结构
解题思路
这道题要求找到两个链表的相交节点。由于链表可能长度不同，但相交后的部分长度相同，我们可以通过以下方法解决：
核心思想
- 计算链表长度：分别遍历两个链表，得到它们的长度
- 对齐起点：让长链表先移动长度差值的步数，使两个链表的剩余长度相等
- 同时遍历：两个指针同时移动，比较节点是否相同
为什么这样有效？
- 如果两个链表相交，那么从相交点到链表末尾的长度是相同的
- 通过让长链表先走差值步，两个指针会同时到达相交点（如果存在）
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *cur1 = headA;
struct ListNode *cur2 = headB;
int a = 0;
int b = 0;
// 计算链表 A 的长度
while(cur1) {
a++;
cur1 = cur1->next;
}
// 计算链表 B 的长度
while(cur2) {
b++;
cur2 = cur2->next;
}
// 重置指针到链表头部
cur1 = headA;
cur2 = headB;
int c = 0;
// 让长链表先移动长度差值的步数
(a > b) {
c = a - b;
(c--) {
cur1 = cur1->next;
}
} {
c = b - a;
(c--) {
cur2 = cur2->next;
}
}
(cur1) {
(cur1 == cur2) {
cur1;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
;
}
