原题链接:PTA | 程序设计类实验辅助教学平台
Tips:以下Python代码仅个人理解,非最优算法,仅供参考!多学习其他大佬的AC代码!
import sys
def main():
# 读取链表头和节点数
h1, h2, n = map(int, sys.stdin.readline().split())
e = [0] * 100010 # 存储数据
ne = [-1] * 100010 # 存储下一个地址
for _ in range(n):
addr, data, next_addr = map(int, sys.stdin.readline().split())
e[addr] = data
ne[addr] = next_addr
L1 = []
L2 = []
# 构建链表L1
p = h1
while p != -1:
L1.append(p)
p = ne[p]
# 构建链表L2
p = h2
while p != -1:
L2.append(p)
p = ne[p]
# 确保L1是长链表
if len(L2) > len(L1):
L1, L2 = L2, L1
# 反转短链表L2
L2.reverse()
# 合并链表
L = []
j = 0
for i in range(len(L1)):
L.append(L1[i])
if (i + 1) % 2 == 0 and j < len(L2):
L.append(L2[j])
j += 1
# 输出结果
for i in range(len(L)):
if i < len(L) - 1:
print(f"{L[i]:05d} {e[L[i]]} {L[i + 1]:05d}")
else:
print(f"{L[i]:05d} {e[L[i]]} -1")
if __name__ == '__main__':
main()
下面是测试点4,答案错误,但不超时(留着以后有空再回来继续想!),想了一会感觉没啥毛病,但问题肯定在合并链表的算法,数据量大的时候可能会漏,还是会错位啥的吧,不管了!上面AC代码直接拿列表装,也不用重新更新指定下一地址了!
import sys
# 定义链表节点的结构
class Node:
def __init__(self, address, data, next_addr):
self.address = address
self.data = data
self.next_addr = next_addr
# 解析输入
def read_input():
head_l1, head_l2, n = sys.stdin.readline().split()
n = int(n)
nodes = {}
for _ in range(n):
address, data, next_addr = sys.stdin.readline().split()
nodes[address] = Node(address, data, next_addr)
return head_l1, head_l2, nodes
# 构建链表并计算长度
def build_linked_list(head_addr, nodes):
current_addr = head_addr
linked_list = []
while current_addr != '-1':
node = nodes[current_addr]
linked_list.append(node)
current_addr = node.next_addr
return linked_list
# 合并链表
def merge_linked_lists(long_list, short_list):
result = []
len_long = len(long_list)
len_short = len(short_list)
long_index = 0
for i in range(len_short):
# 添加长链表的节点
result.append(long_list[long_index])
long_index += 1
if long_index < len_long:
result.append(long_list[long_index])
long_index += 1
# 添加短链表的节点
result.append(short_list[i])
# 将剩余的长链表节点添加到结果中
result.extend(long_list[long_index:])
# 更新所有节点的下一个地址
for k in range(len(result) - 1):
result[k].next_addr = result[k + 1].address
# 最后一个节点的 next_addr 指向 -1
result[-1].next_addr = '-1'
return result
# 输出结果
def output_result(merged_list):
for node in merged_list:
sys.stdout.write(f'{node.address} {node.data} {node.next_addr}\n')
# 主函数
def main():
head_l1, head_l2, nodes = read_input()
# 创建两个链表
list1 = build_linked_list(head_l1, nodes)
list2 = build_linked_list(head_l2, nodes)
len_list1 = len(list1)
len_list2 = len(list2)
if len_list1 >= 2 * len_list2:
# list1 是长链表,list2 是短链表
short_list = list2[::-1] # 逆序短链表
long_list = list1
else:
# list2 是长链表,list1 是短链表
short_list = list1[::-1] # 逆序短链表
long_list = list2
# 合并链表
merged_list = merge_linked_lists(long_list, short_list)
# 打印结果
output_result(merged_list)
# 调用主函数
if __name__ == '__main__':
main()
标签:AC,PAT,addr,list,len,链表,long,result
From: https://blog.csdn.net/m0_56677113/article/details/142916032