1. 找出两个链表的公共结点 【问题描述】给定两个单链表，编写算法找出两个链表的公共结点。 【输入形式】 四行： 第一行：一个数字（第一个单链表中的元素个数） 第二行：第一个单链表中各个结点的值 第三行：一个数字（第二个单链表中的元素个数） 第四行：第二个单链表中各个结点的值 【输出形式】 两行： 第一行：两个单链表的公共元素个数 第二行：依次打印输出各个公共元素 【样例输入】 6 12 5 8 9 -23 16 4 16 21 9 3 【样例输出】 2 9 16 注：若两个链表无公共元素，则输出： 0 没有公共元素

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def findCommonNode(head1, head2):
    """
    :type head1: ListNode
    :type head2: ListNode
    :rtype: List
    """
    len1, len2 = 0, 0
    cur1, cur2 = head1, head2
    # 计算链表长度
    while cur1:
        len1 += 1
        cur1 = cur1.next
    while cur2:
        len2 += 1
        cur2 = cur2.next
    # 对齐链表头
    cur1, cur2 = head1, head2
    if len1 > len2:
        for _ in range(len1 - len2):
            cur1 = cur1.next
    else:
        for _ in range(len2 - len1):
            cur2 = cur2.next
    # 找到公共结点
    common = []
    while cur1 and cur2:
        if cur1 == cur2:
            common.append(cur1.val)
        cur1 = cur1.next
        cur2 = cur2.next
    return common

# 测试
n1 = ListNode(12)
n1.next = ListNode(5)
n1.next.next = ListNode(8)
n1.next.next.next = ListNode(9)
n1.next.next.next.next = ListNode(-23)
n1.next.next.next.next.next = ListNode(16)

n2 = ListNode(16)
n2.next = ListNode(21)
n2.next.next = ListNode(9)
n2.next.next.next = ListNode(3)

common = findCommonNode(n1, n2)
if not common:
    print("0\n没有公共元素")
else:
    print(len(common))
    print(' '.join(map(str, common)))