温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。
题目描述
用C 实现含头结点的单链表，然后实现单链表的两个结点交换位置。
注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换
交换函数定义可以参考：
swap（int pa, int pb) //pa和pb表示两个结点在单链表的位置序号
swap (ListNode * p, ListNode * q) //p和q表示指向两个结点的指针
输入
第1行先输入n表示有n个数据，接着输入n个数据
第2行输入要交换的两个结点位置
第3行输入要交换的两个结点位置
输出
第一行输出单链表创建后的所有数据，数据之间用空格隔开
第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开
第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开
如果发现输入位置不合法，输出字符串error，不必输出单链表
输入样例1
5 11 22 33 44 55 1 4 2 6
输出样例1
11 22 33 44 55 44 22 33 11 55 error
提示
注意要用链表实现哦
思路分析
我们在以及实现了插入和删除的操作的基础上来解决这道题，我使用的是用位置作为参数的方式，首先继续是先判断位置是否非法，非法我直接送走，不过一般不会非法……然后记录下这两个位置的元素，然后删掉这两个位置的元素，然后再在对方的位置上插入自己的元素。
这里需要注意删除的顺序，因为一旦进行删除的操作之后，原有链表的元素逻辑位置会发生一定的变化，所以需要删一个，然后在删除的位置上插一个，然后再删一个，再在删除的位置上插一个。
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
#define OK 0
#define ERROR -1
//结点类定义
class ListNode {
public:
int data;
ListNode * next;
ListNode() {
data = -9999, next = NULL;
}
};
class LinkList {
//带头结点的单链表，位置从0到n，0是头结点，1是首结点，n是尾结点
private:
ListNode * head; //头结点
int size; //表长
public:
LinkList(); //构造函数，创建头结点
~LinkList(); //析构函数，逐个结点回收
int LL_insert(int item, int i); //第i位置插入元素，操作成功或失败返回OK或ERROR
int LL_del(int i); //删除第i位置的元素，操作成功或失败返回OK或ERROR
int LL_get(int i); //获取位置i的元素的数值，查找成功返回数值，查找失败返回ERROR
void LL_print();
void swap(int pa,int pb){
if(pa<1||pb<1||pa>size||pb>size){
cout<<"error"<<endl;
return;
}
int item_a=LL_get(pa),item_b=LL_get(pb);
LL_del(pa);
LL_insert(item_b,pa);
LL_del(pb);
LL_insert(item_a,pb);
LL_print();
} //打印单链表所有数据
};
LinkList::LinkList(): size(0) {
head = new ListNode();
}
LinkList::~LinkList() {
ListNode *p, *q;
p = head->next;
while (p != NULL) {
q = p;
p = p->next;
delete q;
}
size = 0;
head->next = NULL;
}
int LinkList::LL_insert(int item, int i) {
if (i < 1 || i > size 1)
return ERROR;
ListNode*p = head;
int j = 1;
while (j < i) {
p = p->next;
}
ListNode*q = new ListNode();
q->data = item;
q->next = p->next;
p->next = q;
size ;
return OK;
}
int LinkList::LL_del(int i) {
if (i < 1 || i > size)
return ERROR;
ListNode*p = head, *q = head->next;
int j = 1;
while (j < i) {
p = p->next;
q = q->next;
}
p->next = q->next;
delete q;
size--;
return OK;
}
int LinkList::LL_get(int i) {
if (i < 1 || i > size)
return ERROR;
ListNode*p = head->next;
int j = 1;
while (j < i) {
p = p->next;
}
return p->data;
}
void LinkList::LL_print() {
ListNode*p = head->next;
for (int i = 1; i <=size; i ) {
cout << p->data << ' ';
p = p->next;
}
cout << endl;
}
int main() {
int n,item,pa,pb;
LinkList test;
cin>>n;
for(int i=1;i<=n;i ){
cin>>item;
test.LL_insert(item,i);
}
test.LL_print();
for(int i=0;i<2;i ){
cin>>pa>>pb;
test.swap(pa,pb);
}
return 0;
}
