查找两个单向链表的交点

这道题目常规的解决思路是这样的:

  • 计算两个链表 lista1lista2 的长度分别为 len1len2;
  • 比较 len1len2 的大小,先跳过较长的那个链表 |len1 - len2| 个元素(实际就是对齐尾部);
  • 逐个对比 lista1lista2 中的元素,直到找到重合的元素;

当然这是能解决问题的,而且也不复杂。如果这道题用 python 的话,其实可以发挥一下 python 类动态添加属性的特性,优化查找过程。

警告 使用该方法之前自行明确题目考察的目标,不要冒犯考官。

警告 使用该方法之前自行明确题目考察的目标,不要冒犯考官。

警告 使用该方法之前自行明确题目考察的目标,不要冒犯考官。

  • 先遍历一遍其中一个链表,为每一个元素添加一个属性 mark;
  • 遍历另一个链表,如果发现某个元素带有属性 mark,这个元素便是交点;
def func(node1, node2):
    while(node1.next):
       node.mark = True
       node1 = node1.next
    while(node2.next):
       if hasattr(node2, 'mark'):
           return node2
       else:
           node2 = node2.next
    retrun hasattr(node2, 'mark')
Advertisements
此条目发表在Python分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s