OJ2219左移右移（链表）——蓝桥杯2022年国赛

代码为（双向链表）：

#include <bits/stdc++.h>
using namespace std;
struct link {int data;link* prev;link* next;
};
int main()
{int n, m; cin >> n >> m;
link* l = new link();  // 创建头节点，不存储实际数据，仅作为起始点
link* tail = l;        // 尾指针初始指向头节点
unordered_map<int, link*> h;  // 哈希表，用于快速查找任何节点
for (int i = 1; i <= n; i++) {link* p = new link();p->data = i;p->next = nullptr;p->prev = tail;tail->next = p;tail = p;h[i] = p;  // 存储指针到哈希表，以便通过数据值快速定位节点
}
for (int i = 0; i < m; i++) {char c; int a; cin >> c >> a;link* tar = h[a];  // 从哈希表中直接获取目标节点if (c == 'L') {  // 左移操作if (tar->prev->data != 0) {  // 如果已经是第一个实际节点，则不操作if (tar->next != nullptr) {  // 如果不是最后一个节点tar->next->prev = tar->prev;} else {tail = tar->prev;  // 更新尾指针}tar->prev->next = tar->next;  // 从当前位置移除节点// 将节点移至头部tar->next = l->next;l->next->prev = tar;tar->prev = l;l->next = tar;}} else {  // 右移操作if (tar->next != nullptr) {  // 如果不是最后一个节点tar->prev->next = tar->next;tar->next->prev = tar->prev;  // 从当前位置移除节点// 将节点移至尾部tar->next = nullptr;tar->prev = tail;tail->next = tar;tail = tar;  // 更新尾指针}}
}
l = l->next;while (l) {cout << l->data << " ";l = l->next;}return 0;
}

注：

  unordered_map 来实现快速查找节点。

分析：

link* l = new link();  
link* tail = l;       
unordered_map<int, link*> h; 
for (int i = 1; i <= n; i++) {link* p = new link();p->data = i;p->next = nullptr;p->prev = tail;tail->next = p;tail = p;h[i] = p;  
}

这一段代码初始化了链表，从头节点开始，逐个添加节点到链表尾部。同时，在哈希表中保存每个值与对应节点的映射，这样可以在 O(1) 时间复杂度内通过节点值找到对应的链表节点。

for (int i = 0; i < m; i++) {char c; int a; cin >> c >> a;link* tar = h[a];  if (c == 'L') { if (tar->prev->data != 0) {  if (tar->next != nullptr) {  tar->next->prev = tar->prev;} else {tail = tar->prev;  }tar->prev->next = tar->next;  tar->next = l->next;l->next->prev = tar;tar->prev = l;l->next = tar;}} else {  // 右移操作if (tar->next != nullptr) {  tar->prev->next = tar->next;tar->next->prev = tar->prev;  // 将节点移至尾部tar->next = nullptr;tar->prev = tail;tail->next = tar;tail = tar;  }}
}

这段代码处理每个移动操作：

• 左移：将节点移至链表的首部（即头节点的直接后继），确保不是已经在最前面。
• 右移：将节点移至链表的尾部，确保不是已经在最后面。

l = l->next;
while (l) {cout << l->data << " ";l = l->next;
}

最后，从头节点的下一个节点开始，遍历链表并输出每个节点的数据，直到链表结束。