编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
注意:
首先假设 A 、B 两个链表是有相交节点的情况。
再假设 A 、B 两个链表是没有相交节点的情况。
也就是说,无论 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
。
// 登录 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;
}
}
// 登录 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;
}
};
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