求两个交叉链表的交点

59 阅读 0 评论 39 点赞

我是靠谱客的博主虚幻高山，最近开发中收集的这篇文章主要介绍求两个交叉链表的交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

如果两个链表相交，又都不存在环，那么从第一个相交点开始之后的结点都相同（构成了一个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