查找两个链表的第一个交叉结点（Python实现）

题目

给定两个单链表，查找这两个单链表的第一个交叉节点。

例如：链表list_a为：a1→a2→c1→c2→c3，链表list_b为：b1→b2→b3→c1→c2→c3。那么它们第一个交叉结点为c1。

解析

如果两个链表有交叉结点的话，那么交叉节点之后的其他节点都是相同的，即两个链表的结构是Y字型。

   a1→a2↘

         c1→c2→c3

b1→b2→b3↗

可以先获取两个链表的长度，再设定两个指针分别遍历两个链表：让长度较大的链表指针先走|len(list_a)−len(list_b)|步，然后两个指针同步前进，判断第一个相同的结点。

Python实现

# coding=utf-8

class Node(object):

    def __init__(self, value=None, next=None):

        self.value = value

        self.next = next

def get_list_length(head):

    """获取链表长度"""

    length = 0

    while head:

        length += 1

        head = head.next

    return length

def get_intersect_node(list_a, list_b):

    """查找链表第一个交叉结点"""

    length_a = get_list_length(list_a)

    length_b = get_list_length(list_b)

    cur1, cur2 = list_a, list_b

    if length_a > length_b:

        for i in range(length_a - length_b):

            cur1 = cur1.next

    else:

        for i in range(length_b - length_a):

            cur2 = cur2.next

    flag = False

    while cur1 and cur2:

        if cur1.value == cur2.value:

            print(cur1.value)

            flag = True

            break

        else:

            cur1 = cur1.next

            cur2 = cur2.next

    if not flag:

        print('链表没有交叉结点')

if __name__ == '__main__':

    list_a = Node('a1', Node('a2', Node('c1', Node('c2', Node('c3')))))  # 构造不带头结点的链表：a1→a2→c1→c2→c3

    list_b = Node('b1', Node('b2', Node('b3', Node('c1', Node('c2', Node('c3'))))))  # 构造不带头结点的链表：b1→b2→b3→c1→c2→c3

    get_intersect_node(list_a, list_b)

巴特西

查找两个链表的第一个交叉结点（Python实现）

题目

解析

Python实现

最新文章

热门文章