输入一个单向链表,输出该链表中倒数第K个结点,具体实现如下:
#include <iostream> using namespace std; struct LinkNode { public: LinkNode(int value = 0) : nValue(value){ pNext = NULL; } ~LinkNode() { pNext = NULL; } //private: friend class LinkList; int nValue; LinkNode *pNext; }; //带头结点的链表 class LinkList { public: LinkList(); ~LinkList(); void Insert(int nData); //插入元素 void Delete(int nData); //删除元素 void Sort(); //排序 bool IsEmpty(); //判断是否为空 void Reverse(); //反转 void Destroy(); //销毁整个链表 int Length(); //链表长度 LinkNode* Find(int nData); //查找元素 bool IsLoop(); //判断是否为环 void Print(); //打印链表 LinkNode *FindByIndex(int n); //返回链表中第i个元素 LinkNode *FindLastNum(int n); //使用两个指针 高效操作 private: LinkNode *pHead; }; LinkList::LinkList() { pHead = new LinkNode(); } LinkList::~LinkList() { Destroy(); } //从大到小插入 void LinkList::Insert(int nData) { if (pHead == NULL) { cout << "链表未创建!" << endl; return; } LinkNode *pCur = pHead; while (pCur->pNext != NULL) { if (pCur->pNext->nValue < nData) { break; } pCur = pCur->pNext; } LinkNode *pTmp = new LinkNode(nData); pTmp->pNext = pCur->pNext; pCur->pNext = pTmp; } void LinkList::Delete(int nData) { if (pHead == NULL) { cout << "链表未创建!" << endl; return; } if (pHead->pNext == NULL) { cout << "链表为空!" << endl; return; } LinkNode *pCur = pHead; while (pCur->pNext) { if (pCur->pNext->nValue == nData) { LinkNode *pDel = pCur->pNext; pCur->pNext = pCur->pNext->pNext; pDel->pNext = NULL; delete (pDel); } else { pCur = pCur->pNext; } } } void LinkList::Sort() { if (pHead == NULL) { cout << "链表未创建!" << endl; return; } if (pHead->pNext == NULL) { cout << "链表为空!" << endl; } LinkNode *pCur = pHead->pNext; LinkNode *pPre = pHead; LinkNode *pNewHead = new LinkNode(); while (pCur) { LinkNode *pTmp = pCur; pCur = pCur->pNext; //将pTmp结点插入到pNewHead指向的新链表中 LinkNode *p = pNewHead; while (p->pNext) { if (p->pNext->nValue > pTmp->nValue) { break; } p = p->pNext; } pTmp->pNext = p->pNext; p->pNext = pTmp; } delete pHead; pHead = pNewHead; } bool LinkList::IsEmpty() { if (pHead == NULL) { cout << "链表未创建!" << endl; return false; } return pHead->pNext == NULL; } int LinkList::Length() { if (pHead == NULL) { cout << "链表未创建!" << endl; return 0; } int nLength = 0; LinkNode *pCur = pHead->pNext; while (pCur) { nLength++; pCur = pCur->pNext; } return nLength; } void LinkList::Reverse() { if (pHead == NULL) { cout << "链表未创建!" << endl; } if (pHead->pNext == NULL) { cout << "链表为空!" << endl; } 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; } delete pHead; pHead = NULL; } LinkNode* LinkList::Find(int nData) { if (pHead == NULL) { cout << "链表未创建!" << endl; return NULL; } if (pHead->pNext == NULL) { cout << "链表为空!" << endl; return NULL; } LinkNode *pCur = pHead->pNext; while (pCur != NULL) { if (pCur->nValue == nData) { return pCur; } } return NULL; } void LinkList::Print() { if (pHead == NULL) { cout << "链表未创建!" << endl; return; } if (pHead->pNext == NULL) { cout << "链表为空!" << endl; return; } else { LinkNode *pCur = pHead->pNext; while (pCur) { cout << pCur->nValue << " "; pCur = pCur->pNext; } cout << endl; } } bool LinkList::IsLoop() { if (pHead == NULL) { cout << "链表未创建!" << endl; return false; } if (pHead->pNext == NULL) { cout << "链表为空!" << endl; return false; } LinkNode *pFast = pHead->pNext; LinkNode *pLow = pHead->pNext; while (pFast != NULL && pLow != NULL && pFast->pNext != NULL) { pFast = pFast->pNext->pNext; pLow = pLow->pNext; if (pFast == pLow) { return true; } } return false; } LinkNode* LinkList::FindByIndex(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 (pFirst == NULL) { 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.FindByIndex(list.Length() - k); if (p) { cout << p->nValue << endl; } LinkNode *p2 = list.FindLastNum(k); if (p2) { cout << p2->nValue << endl; } system("pause"); return 0; }运行结果如图1所示:
图1 运行效果