单链表合成（去重复值）

将两个递增有序的单链表合并成一个递增有序的单链表，要求利用原表空间（注意重复值只保留一个）。输出合并后的单链表。设数据结点的值域为整型

输入格式:

输入n个有序的整数（无重复值），以0做结束，分别创建单链表A和B；

输出格式:

输出合并后的单链表，数据之间用一个空格分隔。

输入样例:

在这里给出一组输入。例如：

4 6 8 10 0
1 2 3 4 5 6 7 0

输出样例:

在这里给出相应的输出。例如：

1 2 3 4 5 6 7 8 10

# 定义链表节点类
class Node:def __init__(self, data=None):self.data = dataself.next = None# 定义单向链表类
class LinkedList:def __init__(self):self.head = Node()  # 初始化带头结点# 向链表添加节点def append(self, data):new_node = Node(data)cur = self.headwhile cur.next:  # 找到链表的尾部cur = cur.nextcur.next = new_node# 打印链表的所有元素def display(self):cur = self.head.next  # 跳过头结点while cur:print(cur.data, end=" ")cur = cur.nextprint()# 合并两个有序链表@staticmethoddef merge(linked_list_a, linked_list_b):# 创建一个新链表merged_list = LinkedList()cur_a = linked_list_a.head.next  # 跳过头结点cur_b = linked_list_b.head.next  # 跳过头结点last_added = None  # 用于跟踪上一个添加的节点值，以避免重复while cur_a and cur_b:if cur_a.data < cur_b.data:  # A 的节点更小if last_added is None or cur_a.data != last_added:merged_list.append(cur_a.data)last_added = cur_a.datacur_a = cur_a.nextelif cur_a.data > cur_b.data:  # B 的节点更小if last_added is None or cur_b.data != last_added:merged_list.append(cur_b.data)last_added = cur_b.datacur_b = cur_b.nextelse:  # cur_a.data == cur_b.data，两个节点相等if last_added is None or cur_a.data != last_added:merged_list.append(cur_a.data)last_added = cur_a.datacur_a = cur_a.nextcur_b = cur_b.next# 添加剩余节点while cur_a:if last_added is None or cur_a.data != last_added:merged_list.append(cur_a.data)last_added = cur_a.datacur_a = cur_a.nextwhile cur_b:if last_added is None or cur_b.data != last_added:merged_list.append(cur_b.data)last_added = cur_b.datacur_b = cur_b.nextreturn merged_list# 主程序
def main():# 创建第一个链表linked_list_a = LinkedList()input_a = input().split()for num in input_a:num = int(num)if num == 0:breaklinked_list_a.append(num)# 创建第二个链表linked_list_b = LinkedList()input_b = input().split()for num in input_b:num = int(num)if num == 0:breaklinked_list_b.append(num)# 合并两个链表merged_list = LinkedList.merge(linked_list_a, linked_list_b)# 输出合并后的链表merged_list.display()# 调用主程序
main()