写点什么

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 作业