7、实现单链表交换任意两个元素（不包括表头）
题目：实现单链表交换任意两个元素（不包括表头）
分析：假设交换的结点是A与B，那么需要交换A和B的next指针以及AB直接前驱的next指针，需要注意的特殊情况，当A和B相邻时，此时需要特殊处理，如果相同就不交换，如果A和B结点中有一个是表头，也不交换
//实现单链表交换任意两个元素（不包括表头）
#include<iostream>
using namespace std;
typedef struct node
{
int data;
node *next;
}linklist;
linklist *head=NULL;
//创建链表
linklist* CreateList(int* arr,int len)
{
int data;
linklist* pCur,* pRear;
head=(linklist*)malloc(sizeof(linklist));
pRear=head;
int count=0;
while(count<len)
{
pCur=(linklist*)malloc(sizeof(linklist));
pCur->data=arr[count];
pRear->next=pCur;
pRear=pCur;
count++;
}
pRear->next=NULL;
return head;
}
//显示链表
void ShowList(linklist* p)
{
while(p)
{
cout<<p->data <<' ';
p=p->next;
}
cout << endl;
}
/************************************************************************/
/* 假设交换的结点是A与B，那么需要交换A和B的next指针以及AB直接前驱的next指针，
* 需要注意的特殊情况，当A和B相邻时，此时需要特殊处理，如果相同就不交换，如果A和B
* 结点中有一个是表头，也不交换
/************************************************************************/
//找出p的前驱结点
linklist* FindPre(linklist* head,linklist* p)
{
linklist* q=head;
while(q)
{
if(q->next==p)
return q;
else
q=q->next;
}
return NULL;
}
//交换
linklist* Swap(linklist* head,linklist* p,linklist* q)
{
if(head==NULL || p==NULL || q==NULL)
return head;
if(p->data == q->data)
return head;
if(p->next == q)
{
linklist* pPre=FindPre(head,p);
pPre->next=q;
p->next=q->next;
q->next=p;
}
else if(q->next == p)
{
linklist* qPre=FindPre(head,q);
qPre->next=p;
q->next=p->next;
p->next=q;
}
else if(p!=q)
{
linklist* pre_p=FindPre(head,p);
linklist* pre_q=FindPre(head,q);
linklist* after_p=p->next;
p->next=q->next;
q->next=after_p;
pre_p->next=q;
pre_q->next=p;
}
return head;
}
int main()
{
int a[]={3,4,5,1,2,-1,7};
CreateList(a,sizeof(a)/sizeof(a[0]));
ShowList(head->next);
Swap(head,head->next->next,head->next->next->next);
ShowList(head->next);
return 0;
}