http://blog.csdn.net/itcastcpp/article/details/39274891

//尹成 單鏈表操作
#include <iostream>
using namespace std;
class LinkList;struct LinkNode
{
public:LinkNode(int value =0):m_value(value),pNext(NULL){}~LinkNode(){pNext = NULL;}friend class LinkList;int m_value;LinkNode* pNext;
};//帶頭結點的鏈表
class LinkList
{
public:LinkList();~LinkList();void Insert(int data);void Delete(int data);void Sort();bool IsEmpty();void Reverse();void Destroy();int Length();LinkNode* Find(int data);bool IsLoop();void Print();LinkNode* FindIndex(int index);//使用下標LinkNode* FindLastNum(int n);//使用兩個指針
private:LinkNode* pHead;
};LinkList::LinkList()
{pHead = new LinkNode();
}LinkList::~LinkList()
{Destroy();
}//從大到小插入
void LinkList::Insert(int data)
{if(NULL == pHead){cout<<"料表未創建"<<endl;return;}LinkNode* pCur = pHead;//移動到待插入節點的前一個節點while(pCur->pNext != NULL){if(pCur->pNext->m_value < data)break;pCur = pCur->pNext;	}LinkNode* pTmp = new LinkNode(data);pTmp->pNext = pCur->pNext;pCur->pNext = pTmp;
}void LinkList::Delete(int data)
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return;}if(NULL == pHead->pNext){cout<<"鏈表為空"<<endl;return;}LinkNode* pCur = pHead;while(pCur->pNext){//指向要刪除節點的前一個節點if(pCur->pNext->m_value == data){LinkNode* pDel = pCur->pNext;pCur->pNext = pCur->pNext->pNext;pDel = NULL;delete pDel;}elsepCur = pCur->pNext;}
}//從小到大排序
void LinkList::Sort()
{if(pHead == NULL){cout<<"鏈表未創建"<<endl;return;}if(pHead->pNext == NULL){cout<<"鏈表為空"<<endl;return;}LinkNode* pCur = pHead;LinkNode* pNewHead = new LinkNode();while(pCur){LinkNode * pTmp = pCur;pCur = pCur->pNext;LinkNode* p = pNewHead;//將pTmp插入到新的鏈表中 插入時候按照從小到大順序while(p->pNext){if(p->pNext->m_value > pTmp->m_value){break;}p = p->pNext;}if(pTmp != pHead){pTmp->pNext = p->pNext;p->pNext = pTmp;}//delete pHead;//釋放掉原來的內存  這里不注釋掉 導致二次釋放指針？pHead = pNewHead;}
}
bool LinkList::IsEmpty()
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return false;}return pHead->pNext == NULL;
}int LinkList::Length()
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return 0;}int nLength = 0;LinkNode* pCur = pHead->pNext;while(pCur){nLength++;pCur=pCur->pNext;}return nLength;
}void LinkList::Reverse()
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return;}if(pHead->pNext == NULL){cout<<"鏈表為空"<<endl;return;}else{LinkNode* pCur = pHead->pNext->pNext;LinkNode* pPre = pHead->pNext;LinkNode* pnext = NULL;while(pCur){pnext = pCur->pNext;pCur->pNext = pPre;pPre = pCur;pCur = pnext;}pHead->pNext->pNext =NULL;pHead->pNext = pPre;}}void LinkList::Destroy()
{if(pHead == NULL){cout<<"鏈表未創建"<<endl;return;}while(pHead->pNext){LinkNode* pDel = pHead->pNext;pHead->pNext = pDel->pNext;delete pDel;pDel = NULL;}delete pHead;pHead = NULL;
}LinkNode* LinkList::Find(int data)
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return NULL;}if(NULL == pHead->pNext){cout<<"鏈表為空"<<endl;return NULL;}LinkNode* pCur = pHead->pNext;while(pCur){if(pCur->m_value == data)return pCur;pCur= pCur->pNext;	}return NULL;
}void LinkList::Print()
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return;}if(NULL == pHead->pNext){cout<<"鏈表為空"<<endl;return;}else{LinkNode* pCur = pHead->pNext;while(pCur){cout<<pCur->m_value<<" ";pCur = pCur->pNext;}cout<<endl;}
}bool LinkList::IsLoop()
{if(NULL == pHead){cout<<"鏈表未創建"<<endl;return false;}if(NULL == pHead->pNext){cout<<"鏈表為空"<<endl;return false;}LinkNode* pFast = pHead->pNext;LinkNode* pLow = pHead->pNext;//pFast->pNext != NULL 這個條件是很關鍵的while(pFast != NULL &&pLow != NULL && pFast->pNext !=NULL){pFast = pFast->pNext->pNext;pLow = pLow->pNext;if(pFast == pLow)return true;	}return false;
}//返回倒數第n個節點
LinkNode* LinkList::FindIndex(int n)
{if(n <= 0 || n > Length())return NULL;LinkNode* pCur = pHead->pNext;for(int i = 1;i < n;i++){pCur = pCur->pNext;}return pCur;
}//這一種方法利用了中間間隔
LinkNode* LinkList::FindLastNum(int n)
{if(pHead == NULL || pHead->pNext == NULL||n < 0)return NULL;LinkNode* pCur = pHead->pNext;LinkNode* pFirst = pHead->pNext;while(n > 0){pFirst = pFirst->pNext;if(NULL == pFirst)return NULL;n--;}while(pFirst->pNext){pFirst = pFirst->pNext;pCur = pCur->pNext;}return pCur;
}int main()
{LinkList list;  list.Insert(12);  list.Insert(14);  list.Insert(2);  list.Insert(122);  list.Insert(5);  list.Insert(4);  list.Insert(7);  list.Print();  int k;  cout << "請輸入要查詢倒數第幾個結點(計數從0開始):";  cin >> k;  LinkNode *p = list.FindIndex(list.Length() - k);  if (p)  {  cout << p->m_value << endl;  }  LinkNode *p2 = list.FindLastNum(k);  if (p2)  {  cout << p2->m_value << endl;  }cout<<"鏈表進行排序之后的結果:"<<endl;list.Sort();list.Print();return 0;
}