【数据结构与算法】双向链表中查找并与后继结点交换节点值的算法 C++实现（双向链表+循环）

有一个双链表L,设计一个算法查找第一个值为x的结点，将其与后继结点进行交换。

---

思路

在双向链表中查找值为x的节点，并将其与后继节点的值进行交换。首先从链表的头节点开始遍历链表，直到找到值为x的节点或者遍历到链表末尾为止。如果找到了值为x的节点且其后继节点存在，则交换两个节点的值，并返回OK；否则返回ERROR。

时间复杂度为O(n)，其中n为链表的长度，因为最坏情况下可能需要遍历整个链表才能找到对应的节点。空间复杂度为O(1)，因为只需要常数级别的额外空间来存储临时变量。

---

代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using Status = int;
using ElemType = int;const int N = 1e6 + 7;
const int TRUE = 1;
const int FALSE = 0;
const int OK = 1;
const int ERROR = 0;
const int INFEASIBLE = -1;
const int OVERFLOW = -2;int n;
ElemType a[N];struct ListNode {ElemType data;ListNode *prior, *next;
};
using LinkList = ListNode *;Status initList(LinkList &L) {L = (ListNode *)malloc(sizeof(ListNode));if (!L) {return ERROR;}L->prior = NULL;L->next = NULL;return OK;
}Status listInsert(LinkList &L, int pos, ElemType e) {ListNode *p = L;for (int i = 0; p && i < pos; i++) {p = p->next;}if (!p) {return ERROR;}ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));if (!newNode) {return ERROR;}newNode->data = e;newNode->prior = p;newNode->next = p->next;p->next = newNode;if (newNode->next) {newNode->next->prior = newNode;}return OK;
}ElemType getElem(LinkList L, int pos) {ListNode *p = L->next;for (int i = 0; p && i < pos; i++) {p = p->next;}if (!p) {return NULL;}return p->data;
}Status findAndSwap(LinkList &L, int x) {ListNode *p = L;while (p && p->data != x) {p = p->next;}if (!p || !p->next) {return ERROR;}swap(p->data, p->next->data);return OK;
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}LinkList L;initList(L);for (int i = 0; i < n; i++) {listInsert(L, i, a[i]);}for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";findAndSwap(L, 3);for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";return 0;
}