Week 08 作业
发布于: 2020 年 07 月 29 日
判断是否重合:
单链表如果合并,则相交节点后的所有节点为两个链表共有元素。则最后一个节点肯定相同,因此只需要判断两个链表最后一个节点是否相同。
如果合并,找合并节点 x:
让长链表先走(len(长链表) - len(短链表))步,然后一起走,则第一个相交的元素为 x
class Node:
def __init__(self, data):
self.data = data
self.next = None
def is_intersect(l1, l2):
if l1 is None or l2 is None:
return False
p1, p2 = l1, l2
last1, last2 = None, None
while p1.next is not None:
last1 = p1
p1 = p1.next
while p2.next is not None:
last2 = p2
p2 = p2.next
return True if last1 == last2 else False
def find_first_cross_node(l1, l2):
p1, p2 = l1, l2
len1, len2 = 0, 0
while p1.next:
len1 += 1
p1 = p1.next
while p2.next:
len2 += 1
p2 = p2.next
if len1 > len2:
tmp_len = len1 - len2
for _ in range(tmp_len):
l1 = l1.next
for _ in range(len1 - tmp):
if l1 == l2:
return l1
l1 = l1.next
l2 = l2.next
else:
tmp_len = len2 - len1
for _ in range(tmp_len):
l2 = l2.next
for _ in range(len2 - tmp):
if l1 == l2:
return l2
l1 = l1.next
l2 = l2.next
复制代码
划线
评论
复制
发布于: 2020 年 07 月 29 日阅读数: 50
鱼_XueTr
关注
还未添加个人签名 2019.04.19 加入
还未添加个人简介
评论