学步园

头文件：list.h

<pre name="code" class="cpp">#ifndef LIST_H
#define LIST_H
#include <iostream>
using namespace std;

/* Define a structure for linked list element */
typedef struct ListElmt_
{
	int data;
	struct ListElmt_ *next;
}ListElmt_;

void initList(ListElmt_ *&pList);
int getListLength(ListElmt_ *pList);
void insertNode(ListElmt_ *&pList, int pos, int data);
void displayList(ListElmt_ *pList);
void sortLinkList(ListElmt_ *pList);
void deleteList(ListElmt_ *&pList, int pos);
ListElmt_ * reverseLinkList(ListElmt_ *pList);
ListElmt_ * getKthDataFromEnd(ListElmt_ *pList, int k);
#endif

函数：mylist.cpp

<pre name="code" class="cpp">#include "list.h"

void initList(ListElmt_ *&pList)
{
	if (NULL == pList)
	{
		return;
	}
	delete []pList;
	pList = NULL;
	return;
}

int getListLength(ListElmt_ *pList)
{
	int nLen = 0;
	for (ListElmt_ *p = pList; p != NULL; p = p->next)
	{
		++nLen;
	}
	return nLen;
}

void insertNode(ListElmt_ *&pList, int pos, int data)
{
	if (pos < 0)
	{
		return;
	}
	ListElmt_ *pNewNode = new ListElmt_;
	if (NULL == pNewNode)
	{
		return;
	}
	pNewNode->data = data;
	ListElmt_ *pTmp = NULL;
	int nPosCount = 0;
	int nListLength = getListLength(pList);
	if (0 == nListLength)
	{
		pList = pNewNode;
		pNewNode->next = NULL;
		return;
	}
	if (0 == pos)
	{
		ListElmt_ *p = pList;
		pNewNode->next = p;
		pList = pNewNode;
	}
	else if (pos >= nListLength - 1)
	{
		pTmp = pList;
		while(pTmp->next != NULL)
		{
			pTmp = pTmp->next;
		}
		pNewNode->next = NULL;
		pTmp->next = pNewNode;
	}
	else
	{
		for (pTmp = pList; pTmp != NULL; pTmp = pTmp->next)
		{
			if (nPosCount == pos - 1)
			{	
				ListElmt_ *q= pTmp->next;
				pTmp->next = pNewNode;
				pNewNode->next = q;
			}

			++nPosCount;
		}
	}
}

void deleteList(ListElmt_ *&pList, int pos)
{
	if (NULL == pList || pos < 0)
	{
		return;
	}
	int nLen = getListLength(pList);

	if (pos == 0)
	{
		ListElmt_ *p = pList;
		ListElmt_ *q = pList->next;
		delete p;
		pList = q;
	}
	else if (pos > nLen - 1)
	{
		cout << "No Element to delete!!!" << endl;
	}
	else
	{
		ListElmt_ *p = pList;
		int nCnt = 0;
		for (; p != NULL; p = p->next)
		{
			if(pos == nCnt + 1)
			{
				ListElmt_ *q = p->next;
				p->next = q->next;
				delete q;
			}
			nCnt++;
		}
	}
}

void displayList(ListElmt_ *pList)
{
	if (NULL == pList)
	{
		cout << "list is empty!" << endl;
	}

	for (ListElmt_* p = pList; p != NULL; p = p->next)
	{
		cout << p->data << '\t';
	}
	cout << endl;
}

// 链表反转
ListElmt_ * reverseLinkList(ListElmt_ *pList)
{
	ListElmt_ * pPrevNode = NULL; // 当前结点的前一个结点
	ListElmt_ * pCurNode  = pList; // 当前结点

	while (pCurNode != NULL)
	{
		ListElmt_ * pNext = pCurNode->next;
		
		pCurNode->next = pPrevNode;  // 当前结点指向前一个结点
		
		pPrevNode = pCurNode;        // 当前和前一点顺序移位
		pCurNode  = pNext; 
	}
	return pPrevNode;
}

ListElmt_ * getKthDataFromEnd(ListElmt_ *pList, int k)
{
	if (NULL == pList || k <= 0)
	{
		return NULL;
	}
	
	ListElmt_ * pNode           = pList;
	ListElmt_ * pKthNodeFromEnd = pList;

	while (k - 1 > 0)
	{
		if (pNode->next != NULL)
		{
			pNode = pNode->next;
			--k;
		}
		else
		{
			return NULL;
		}
	}

	while (pNode->next != NULL)
	{
		pNode           = pNode->next;
		pKthNodeFromEnd = pKthNodeFromEnd->next;
	}
	return pKthNodeFromEnd;
}

void sortLinkList(ListElmt_ *pList)
{
	if (NULL == pList)
	{
		return;
	}
	ListElmt_ *p = pList;
	ListElmt_ *q = pList->next;
	for (; p != NULL; p = p->next)
	{
		for (q = p->next; q != NULL; q = q->next)
		{
			if (p->data > q->data)
			{
				int tmp = p->data;
				p->data = q->data;
				q->data = tmp;
			}
		}
	}
}

测试函数：main.cpp

<pre name="code" class="cpp">#include "list.h"


int main()
{
	cout << "构造链表！！！" << endl;
	ListElmt_ *pData = NULL;
	int nPos = 0;
	for (int i = 100; i > 0; i /= 2)
	{
		insertNode(pData, nPos, i);
		nPos++;
	}
	insertNode(pData, 0, 9999);
	insertNode(pData, 100, 122);
	insertNode(pData, 3, 223);
	displayList(pData);
	sortLinkList(pData);
 	displayList(pData);
// 	deleteList(pData, 0);
// 	displayList(pData);
// 	initList(pData);
// 	displayList(pData);
// 	deleteList(pData, 1);
// 	displayList(pData);

	ListElmt_ * pRes = reverseLinkList(pData);
	displayList(pRes);
	ListElmt_ *pResNode = getKthDataFromEnd(pRes, 100);
	if (pResNode == NULL)
	{

	}
	else
	{
		cout << pResNode->data << endl;
	}
	
	return 0;
}

</pre><pre name="code" class="cpp">测试结果：