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

 关注
发布于: 2020 年 07 月 27 日
题目
两个单向链表，这两个链表有可能在某个元素合并(链表长度分别为m、n)，如下图，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速判断两个链表是否合并？如果合并，找到合并的元素，即图中的x元素。
﻿
解题思路
最简单的方法，也是最容易想到的方法是暴力遍历，即对于链表1的每一个节点，遍历链表2，看是否指向同一个节点。这种方法空间复杂度为1，但是时间复杂度为O(mn)。
但是，仔细观察链表。如果两个链表长度相同，那么同时移动两个链表的指针，那么会同时到达合并的节点。
那么，如果两个链表长度不相同。对于长的链表的头指针，移动两个链接的长度差，就可以得到两个长度相同的链表。
因此，算法可以分为两个阶段：
得到两个链表的长度
长的链表头指针移动一个长度差。接着，两个链表的指针同时向下移动，如果指向同一个节点，则该节点为合并的节点。
代码
定义节点
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
运行结果符合预期。
﻿