算法训练营第一期 | 相交链表
一、题目描述
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
注意：
- 如果两个链表没有交点，返回 null。
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
二、题目解析
1、模拟
首先假设 A 、B 两个链表是有相交节点的情况。
再假设 A 、B 两个链表是没有相交节点的情况。
2、规律
也就是说，无论 A、B 两个链表是否有相交点，最终都会指向一个相同的节点，要么是它们的公共尾部，要么是 NULL。
让指针 pointA 和 pointB 分别指向链表 A 和链表 B 的头结点，之后两个指针分别以步幅为 1 的速度向链表的尾部遍历。
- 当指针
pointA遍历到链表 A 的尾节点时，此时指针pointA走了 a 个节点，将指针pointA指向链表 B 的头部，继续向后遍历，直至走到c1，此时指针pointA总共走了a + ( b - c )步。 - 当指针
pointB遍历到链表 B 的尾节点时，此时指针pointB走了 b 个节点，将指针pointB指向链表 A 的头部，继续向后遍历，直至走到c1，此时指针pointB总共走了b + ( a - c )步。
根据数学知识，a + ( b - c ) = b + ( a - c ) ，如果 c > 0，表明两链表有公共尾部， c1 存在，两两链表同时到达 c1；如果 c = 0，表明两链表没有公共尾部，指针 pointA 和 pointB 都指向 NULL。
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 边界判断
if (headA == null || headB == null) return null;
// 设置一个指针 pointA，指向链表 A 的头节点
ListNode pointA = headA;
// 设置一个指针 pointB，指向链表 B 的头节点
ListNode pointB = headB;
// 指针 pointA 和 指针 pointB 不断向后遍历，直到找到相交点
// 不用担心会跳不出这个循环，实际上在链表 headA 长度和链表 headB 长度的之和减一
// pointA 和 pointB 都会同时指向 null
// 比如 headA 的长度是 7，headB 的长度是 11，这两个链表不相交
// 那么 pointA 移动了 7 + 11 - 1 次之后，会指向 null
// pointB 移动了 7 + 11 - 1 次之后，也指向 null
// 这个时候就跳出了循环
while (pointA != pointB) {
// 指针 pointA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上
if( pointA == null){
// 指针 pointA 跳转到链表 B 上
pointA = headB;
}else{
// 否则的话 pointA 不断的向后移动
pointA = pointA.next;
}
// 指针 pointB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上
if( pointB == null){
// 指针 pointA 跳转到链表 B 上
pointB = headA;
}else{
// 否则的话 pointB 不断的向后移动
pointB = pointB.next;
}
}
// 1、此时，pointA 和 pointB 指向那个相交的节点，返回任意一个均可
// 2、此时，headA 和 headB 不相交，那么 pointA 和 pointB 均为 null，也返回任意一个均可
return pointA;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 边界判断
if (headA == NULL || headB == NULL) return NULL;
// 设置一个指针 pointA，指向链表 A 的头节点
ListNode *pointA = headA;
// 设置一个指针 pointB，指向链表 B 的头节点
ListNode *pointB = headB;
// 指针 pointA 和 指针 pointB 不断向后遍历，直到找到相交点
// 不用担心会跳不出这个循环，实际上在链表 headA 长度和链表 headB 长度的之和减一
// pointA 和 pointB 都会同时指向 null
// 比如 headA 的长度是 7，headB 的长度是 11，这两个链表不相交
// 那么 pointA 移动了 7 + 11 - 1 次之后，会指向 null
// pointB 移动了 7 + 11 - 1 次之后，也指向 null
// 这个时候就跳出了循环
while (pointA != pointB) {
// 指针 pointA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上
if( pointA == NULL){
// 指针 pointA 跳转到链表 B 上
pointA = headB;
}else{
// 否则的话 pointA 不断的向后移动
pointA = pointA->next;
}
// 指针 pointB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上
if( pointB == NULL){
// 指针 pointA 跳转到链表 B 上
pointB = headA;
}else{
// 否则的话 pointB 不断的向后移动
pointB = pointB->next;
}
}
// 1、此时，pointA 和 pointB 指向那个相交的节点，返回任意一个均可
// 2、此时，headA 和 headB 不相交，那么 pointA 和 pointB 均为 null，也返回任意一个均可
return pointA;
}
};
3、Python 代码
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 边界判断
if( headA == None or headB == None ):
return None
# 设置一个指针 pointA，指向链表 A 的头节点
pointA = headA
# 设置一个指针 pointB，指向链表 B 的头节点
pointB = headB
# 指针 pointA 和 指针 pointB 不断向后遍历，直到找到相交点
# 不用担心会跳不出这个循环，实际上在链表 headA 长度和链表 headB 长度的之和减一
# pointA 和 pointB 都会同时指向 null
# 比如 headA 的长度是 7，headB 的长度是 11，这两个链表不相交
# 那么 pointA 移动了 7 + 11 - 1 次之后，会指向 null
# pointB 移动了 7 + 11 - 1 次之后，也指向 null
# 这个时候就跳出了循环
while pointA != pointB:
# 指针 pointA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上
if pointA == None:
# 指针 pointA 跳转到链表 B 上
pointA = headB
else:
# 否则的话 pointA 不断的向后移动
pointA = pointA.next
# 指针 pointB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上
if pointB == None:
# 指针 pointA 跳转到链表 B 上
pointB = headA
else:
# 否则的话 pointB 不断的向后移动
pointB = pointB.next
# 1、此时，pointA 和 pointB 指向那个相交的节点，返回任意一个均可
# 2、此时，headA 和 headB 不相交，那么 pointA 和 pointB 均为 null，也返回任意一个均可
return pointA
