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 加入
还未添加个人简介











评论