7单链表交换任意两个元素（不包括表头）

//单链表交换任意两个元素(不包括表头)
#include <iostream>
using namespace std;

struct LinkNode
{
LinkNode *pNext;
int nValue;
LinkNode(int value = 0)
{
nValue = value;
pNext = NULL;
}
};

class Linklist
{
public:
Linklist(){ pHead = new LinkNode(); };
~Linklist(){ delete pHead;}; 
void InsertValue(int nValue);
void Reverse();
void Reverse2();
LinkNode *FindLastNum(int nNum);
LinkNode *FindMidNode(bool &IsOdd);
void DeleteNode(LinkNode *pDel);
Linklist* Mergelist(const Linklist &list) const;
void SwapNode(LinkNode *p1, LinkNode *p2);
void Print();

private:
LinkNode *pHead;
};


void Linklist::InsertValue(int nValue)
{
if (pHead == NULL)
{
return;
}
LinkNode *pCur = pHead;
while (pCur->pNext != NULL)
{
pCur = pCur->pNext;
}

LinkNode *pTmp = new LinkNode(nValue);
pCur->pNext = pTmp;
}

void Linklist::Reverse()
{
if (pHead == NULL)
{
return;
}

//特殊情况:如果链表为空或者只有一个元素，直接返回
if (pHead->pNext == NULL || pHead->pNext->pNext == NULL)
{
return;
}

LinkNode *pPre = pHead;
LinkNode *pCur = pHead->pNext;
LinkNode *pNext;

while (pCur != NULL)
{
pNext = pCur->pNext;
pCur->pNext = pPre;
pPre = pCur;
pCur = pNext;
}

pHead->pNext->pNext = NULL;
pHead->pNext = pPre;
}

void Linklist::Reverse2()
{
if (pHead == NULL)
{
return;
}

//特殊情况:如果链表为空或者只有一个元素，直接返回
if (pHead->pNext == NULL || pHead->pNext->pNext == NULL)
{
return;
}

LinkNode *pCur = pHead->pNext;
LinkNode *pNext = NULL;
LinkNode *pNextNext = NULL;

while (pCur->pNext != NULL)
{
pNext = pCur->pNext;
pNextNext = pNext->pNext;

pNext->pNext = pHead->pNext;
pHead->pNext = pNext;
pCur->pNext = pNextNext;
}
}

LinkNode *Linklist::FindLastNum(int nNum)
{
if (pHead == NULL)
{
return NULL;
}
LinkNode *pFirst = pHead;
int i = 0;
while (i < nNum)
{
if (pFirst == NULL)
{
return NULL;
}
pFirst = pFirst->pNext;
i++;
}
LinkNode *pSecond = pHead;
while (pFirst != NULL)
{
pFirst = pFirst->pNext;
pSecond = pSecond->pNext;
}

return pSecond;
}

//考虑链表个数为奇数Odd、偶数Even两种情况
LinkNode* Linklist::FindMidNode(bool &IsOdd)
{
if (pHead == NULL)
{
return NULL;
}
LinkNode *pFirst = pHead;
LinkNode *pSecond = pHead;

while (pFirst != NULL && pFirst->pNext != NULL)
{
pFirst = pFirst->pNext->pNext;
pSecond = pSecond->pNext;
}
if (pFirst == NULL)
{
IsOdd = true;
}
else
{
IsOdd = false;
}
return pSecond;
}

void Linklist::DeleteNode(LinkNode *pDel)
{
if (pHead == NULL || pDel == NULL)
{
return;
}

//如果要删除的节点不是最后一个节点
if (pDel->pNext != NULL)
{
pDel->nValue = pDel->pNext->nValue;
LinkNode *pTmp = pDel->pNext;
pDel->pNext = pTmp->pNext;

delete pTmp;
}
else
{
LinkNode *pCur = pHead->pNext;
while (pCur != NULL)
{
if (pCur->pNext = pDel)
{
pCur->pNext = NULL;
delete pDel;
}
else
{
pCur = pCur->pNext;
}
}
}
}

Linklist*  Linklist::Mergelist(const Linklist &list) const
{
Linklist *pList = new Linklist;
if (pList == NULL || pHead == NULL || list.pHead == NULL)
{
return NULL;
}

LinkNode *pCur1 = pHead->pNext;
LinkNode *pCur2 = list.pHead->pNext;
LinkNode *pCur3 = pList->pHead;

while (pCur1 && pCur2)
{
if (pCur1->nValue > pCur2->nValue)
{
pList->InsertValue(pCur2->nValue);
pCur2 = pCur2->pNext;
}
else
{
pList->InsertValue(pCur1->nValue);
pCur1 = pCur1->pNext;
}
}
while (pCur1)
{
pList->InsertValue(pCur1->nValue);
pCur1 = pCur1->pNext;
}
while (pCur2)
{
pList->InsertValue(pCur2->nValue);
pCur2 = pCur2->pNext;
}

return pList;
}

//需要三个额外指针变量
void Linklist::SwapNode(LinkNode *p1, LinkNode *p2)
{
if (pHead == NULL || p1 == NULL || p2 == NULL)
{
return;
}
if (p1 == p2)
{
return;
}
LinkNode *pCur = pHead->pNext;
LinkNode *pCur1 = p1;
LinkNode *pCur2 = p2;
LinkNode *pPre1 = NULL;
LinkNode *pPre2 = NULL;
int nCount = 0;
while (pCur)
{
if (pCur->pNext == pCur1)
{
pPre1 = pCur;
nCount++;
if (nCount == 2)
{
break;
}
}
if (pCur->pNext == pCur2)
{
pPre2 = pCur;
nCount++;
if (nCount == 2)
{
break;
}
}
pCur = pCur->pNext;
}
pCur = pCur1->pNext;

pPre1->pNext = pCur2;
pCur1->pNext = pCur2->pNext;
pPre2->pNext = pCur1;
pCur2->pNext = pCur;
}

void Linklist::Print()
{
if (pHead == NULL)
{
return;
}
LinkNode *pCur = pHead->pNext;
while (pCur != NULL)
{
cout<<pCur->nValue<<" ";
pCur = pCur->pNext;
}
cout<<endl;
}


int main()
{
Linklist list;
int nArr[] = {12,13,43,1,2,4,55,23};
for (int i = 0; i < 8; i++)
{
list.InsertValue(nArr[i]);
}
list.Print();

LinkNode *p1 = list.FindLastNum(3);
LinkNode *p2 = list.FindLastNum(4);
if (p1 != NULL && p2 != NULL)
{
list.SwapNode(p1, p2);
}
list.Print();
return 0;
}