题解 | 插队

#include <iostream>
#include <unordered_map> 
using namespace std;
//顾客人数n，每个人的名字，插队次数m，构建链表，有哨兵节点,进行链表间的插入，删除操作
struct ListNode {
 	string val;
 	struct ListNode *next;
 	ListNode(string x) : val(x), next(nullptr) {}//构造函数 
  };
int main(){
	ios::sync_with_stdio(false);//关闭iostream and stdio的同步，加速输入输出
	cin.tie(nullptr); 
	int n, m;
	string s, x,y;
//哨兵节点
	ListNode *dummy = new ListNode("");
	ListNode *vhead = dummy;
	//哈希表存储【名字 -》该节点的前驱节点指针】 
	unordered_map<string, ListNode*> name2prev; 
//构建原始链表+初始化哈希表 
		cin >> n >> m;
	while (n--){
	cin >> s;
	vhead->next = new ListNode(s);
	name2prev[s] = vhead; //记录当前节点的前驱 
	vhead = vhead->next;
		}
	//进行插队操作
	while (m--){
	cin >> x >> y;//x跑到y前面
	//边界
	if (x == y) continue;
	if (name2prev.find(x) == name2prev.end()) continue; 
	//找到X节点进行删除
	ListNode *x_prev = name2prev[x];
	ListNode *x_node = x_prev->next;
	x_prev->next = x_node->next;//断开x节点
	//更行哈希表：x的后继节点的前驱变成前驱接待你
	if (x_node->next != nullptr) {
		name2prev[x_node->next->val] = x_prev;
	} 
	delete x_node;
	name2prev.erase(x);
	// 边界y不存在，将x插入到链表尾部
	 
	//进行插入操作
	ListNode *y_prev = name2prev[y];
	ListNode *ins_node = new ListNode(x);
	ins_node->next = y_prev->next;
	y_prev->next = ins_node;
	//跟新哈希表：x的前驱是y_prev,y的前驱变成x
	name2prev[x] = y_prev;
	name2prev[y] = ins_node; 
	}
	//输出插完队的链表
	ListNode* result = dummy ->next;
	while(result!= nullptr){
		cout <<result->val<<" ";
		result = result->next;
	}
	//释放链表内存（避免内存泄露） 
	ListNode *cur = dummy;
	while (cur!= nullptr) {
		ListNode* temp = cur;
		cur = cur->next;
		delete temp;
	}
return 0;
}
// 64 位输出请用 printf("%lld")
//效率低下