架构师训练营 1 期 -- 第八周作业

import math
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
def check_linked_list(list_1, list_2):
    """
    检查两个链表是否相交，思路是遍历两个节点，获取他们的长度，并判断最后一个节点是否相同。如果最后一个节点相同，则链表相交。
    然后找出相交节点，计算两个链表的[长度差]，将长链表节点后移[长度差]位后，依次比较节点是否相同，第一个相同的节点几位相交节点。
    :param list_1:
    :param list_2:
    :return:
    """
    # 计算两个链表长度以及最后一个节点
    length_1 = 0
    length_2 = 0
    last_node_1 = Node
    last_node_2 = Node
    # 计算链表1长度以及最后节点
    current_node = list_1.head
    while current_node:
        length_1 = length_1 + 1
        if current_node.next is None:
            last_node_1 = current_node
        current_node = current_node.next
    # 计算链表2长度以及最后节点
    current_node = list_2.head
    while current_node:
        length_2 = length_2 + 1
        if current_node.next is None:
            last_node_2 = current_node
        current_node = current_node.next
    # 如果最后节点相同，则链表相交，否则不相交
    if last_node_1 == last_node_2:
        print('链表相交')
        node_1 = list_1.head
        node_2 = list_2.head
        # 求长度差length_diff
        length_diff = int(math.fabs(length_1 - length_2))
        # 将长的链表后移length_diff位
        if length_1 > length_2:
            for i in range(length_diff):
                node_1 = node_1.next
        else:
            for i in range(length_diff):
                node_2 = node_2.next
        # 找出相交节点，如果两个链表节点相同，则为相交节点，退出循环。
        while node_1 and node_2:
            if node_1 is node_2:
                print('链表相交节点【', node_1.data, '】')
                break
            node_1 = node_1.next
            node_2 = node_2.next
    else:
        print('链表不相交')
    pass
def construct_linked_list():
    node_a = Node('a')
    node_b = Node('b')
    node_d = Node('d')
    node_e = Node('e')
    node_f = Node('f')
    node_x = Node('x')
    node_y = Node('y')
    node_z = Node('z')
    node_a.next = node_b
    node_b.next = node_x
    node_x.next = node_y
    node_y.next = node_z
    node_d.next = node_e
    node_e.next = node_f
    node_f.next = node_x
    list_1 = LinkedList()
    list_1.head = node_a
    list_2 = LinkedList()
    list_2.head = node_d
    return list_1, list_2
def print_list(list):
    current_node = list.head
    while current_node:
        print(current_node.data, end='\t')
        current_node = current_node.next
    print()
if __name__ == '__main__':
    list_1, list_2 = construct_linked_list()
    print('链表信息：')
    print_list(list_1)
    print_list(list_2)
    check_linked_list(list_1, list_2)
    pass