DS单链表--结点交换 C++

温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。

目录

题目描述

思路分析

AC代码 

---

题目描述

用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代码 

#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;
}