题解 | 插队

from typing import Optional


class ListNode:
    def __init__(self, val: str):
        self.val = val
        self.prev: Optional["ListNode"] = None
        self.next: Optional["ListNode"] = None


head = ListNode("")
head.next = head
head.prev = head
p = head
node_dict = {}

n, m = list(map(int, input().split()))
s = input().split()

for val in s:
    node = ListNode(val)
    node_dict[val] = node
    p.next = node
    node.prev = p
    p = p.next
p.next = head
head.prev = p

for _ in range(m):
    x, y = input().split()
    x_node = node_dict[x]
    y_node = node_dict[y]

    x_node.prev.next = x_node.next
    x_node.next.prev = x_node.prev

    x_node.prev = y_node.prev
    x_node.next = y_node

    y_node.prev.next = x_node
    y_node.prev = x_node


p = head.next
while p != head:
    print(p.val, end=" ")
    p = p.next