算法题:链表的第一个合并节点

用户头像
破晓_dawn
关注
发布于: 16 小时前

题目

两个单向链表,这两个链表有可能在某个元素合并(链表长度分别为m、n),如下图,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速判断两个链表是否合并?如果合并,找到合并的元素,即图中的x元素。




解题思路

最简单的方法,也是最容易想到的方法是暴力遍历,即对于链表1的每一个节点,遍历链表2,看是否指向同一个节点。这种方法空间复杂度为1,但是时间复杂度为O(mn)。

但是,仔细观察链表。如果两个链表长度相同,那么同时移动两个链表的指针,那么会同时到达合并的节点。

那么,如果两个链表长度不相同。对于长的链表的头指针,移动两个链接的长度差,就可以得到两个长度相同的链表。

因此,算法可以分为两个阶段:

  1. 得到两个链表的长度

  2. 长的链表头指针移动一个长度差。接着,两个链表的指针同时向下移动,如果指向同一个节点,则该节点为合并的节点。


代码

定义节点

class Node(object):
"""链表中的节点"""
def __init__(self, content, next_node):
self.content = content
self.next = next_node
def __str__(self):
if self.next:
return "%s->%s" % (self.content, self.next)
else:
return "%s->%s" % (self.content, None)
def create_link(list_1, list_2, merge_list):
"""创建链表
list1 = list_1 + merge_list
list2 = list_2 + merge_list
"""
merge_node = add_nodes(merge_list, None)
print "merge_node: ", merge_node
list_1_first = add_nodes(list_1, merge_node)
print "list_1_first", list_1_first
list_2_first = add_nodes(list_2, merge_node)
print "list_2_first", list_2_first
return list_1_first, list_2_first
def add_nodes(list_num, last_node):
"""给定链表头,在链表头之前,加入新的元素
list_num: 需要插入的元素
last_node: 插入的链表的头
"""
now_next = last_node
if list_num:
for i in xrange(len(list_num), 0, -1):
temp_node = Node(list_num[i-1], now_next)
now_next = temp_node
return temp_node
else:
return now_next

查找第一个合并的节点

def find_merge_node(start_node_x, start_node_y):
"""
给定链表头,发现两个链表是否合并?不合并返回None,合并返回合并的第一个元素。
"""
len_x = get_node_len(start_node_x)
len_y = get_node_len(start_node_y)
if len_x > len_y:
long_node = start_node_x
short_node = start_node_y
else:
long_node = start_node_y
short_node = start_node_x
for _ in xrange(0, abs(len_x - len_y)):
long_node = long_node.next
while long_node and short_node:
if long_node == short_node:
return long_node
long_node = long_node.next
short_node = short_node.next
return None
def get_node_len(start_node):
"""获得链表长度"""
link_len = 0
temp_node = start_node
while temp_node:
link_len += 1
temp_node = temp_node.next
return link_len

测试:

link_1, link_2 = create_link(list_1=['a', 'b'], list_2=['d','e', 'f'], merge_list=['x', 'y', 'z'])
merge_node = find_merge_node(link_1, link_2)
print "result:", merge_node.content

运行结果:

result: x

运行结果符合预期。



发布于: 16 小时前 阅读数: 7
用户头像

破晓_dawn

关注

慢慢,稳稳 2017.12.06 加入

业余选手,但是有一颗向往专业的心

评论

发布
暂无评论
算法题:链表的第一个合并节点