如果两个链表相交，又都不存在环，那么从第一个相交点开始之后的结点都相同（构成了一个Y型）。
因此，只要分别遍历这两个链表，找到末尾结点，如果末尾结点相同，即可确认相交。
如果要求这种情况的交点，由于相交部分全部都相同，所以彼此的长度差异存在于相交之前的部分。因此，只需要先得到两个链表的差d，然后将较长的链表截去前d个结点；此时，两个链表同时出发向后遍历，第一个相等的结点即为交点。
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def node(l1, l2):
length1, lenth2 = 0, 0
# 求两个链表长度
while l1.next:
l1 = l1.next
length1 += 1
while l2.next:
l2 = l2.next
length2 += 1
# 长的链表先走
if length1 > lenth2:
for _ in range(length1 - length2):
l1 = l1.next
else:
for _ in range(length2 - length1):
l2 = l2.next
while l1 and l2:
if l1.next == l2.next:
return l1.next
else:
l1 = l1.next
l2 = l2.next
最后
以上就是虚幻高山最近收集整理的关于求两个交叉链表的交点的全部内容，更多相关求两个交叉链表内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复