Week 08 作业

用户头像
鱼_XueTr
关注
发布于: 2020 年 07 月 29 日
Week 08 作业



判断是否重合:

  • 单链表如果合并,则相交节点后的所有节点为两个链表共有元素。则最后一个节点肯定相同,因此只需要判断两个链表最后一个节点是否相同。

如果合并,找合并节点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



用户头像

鱼_XueTr

关注

还未添加个人签名 2019.04.19 加入

还未添加个人简介

评论

发布
暂无评论
Week 08 作业