1、删除链表节点
int DeleteLinkList(LinkNode *pHead, DataType TmpData)
{LinkNode *pPreNode = NULL;LinkNode *pTmpNode = NULL;int cnt = 0;pPreNode = pHead;pTmpNode = pHead->pNext;while (pTmpNode != NULL){if (pTmpNode->Data == TmpData){//删除pPreNode->pNext = pTmpNode->pNext;free(pTmpNode);pTmpNode = pPreNode->pNext;cnt++;}else {pTmpNode = pTmpNode->pNext;pPreNode = pPreNode->pNext;}}return cnt;
}
2、销毁链表
int DestroyLinkList(LinkNode **ppHead)
{LinkNode *pTmpNode = NULL;LinkNode *pFreeNode = NULL;pTmpNode = pFreeNode = *ppHead;while (pTmpNode != NULL){pTmpNode = pTmpNode->pNext;free(pFreeNode);pFreeNode = pTmpNode;}*ppHead = NULL;return 0;
}
3、寻找链表的中间节点位置
LinkNode *FindMidLinkNode(LinkNode *pHead)
{LinkNode *pFast = NULL;LinkNode *pSlow = NULL;pFast = pSlow = pHead->pNext;while (pFast != NULL){pFast = pFast->pNext;if (NULL == pFast){break;}pFast = pFast->pNext;if (NULL == pFast){break;}pSlow = pSlow->pNext;}return pSlow;
}
功能:找到中间节点位置
算法原理:
快指针pFast每次走2步,慢指针pSlow每次走1步,快指针到达末尾时,慢指针所在的位置即为中间位置 。
4、寻找链表倒数第K个节点
LinkNode *FindLastKthLinkNode(LinkNode *pHead, int k)
{LinkNode *pFast = pHead->pNext;LinkNode *pSlow = pHead->pNext;int i = 0;for (i = 0; i < k; i++){pFast = pFast->pNext;if (NULL == pFast){break;}}if (NULL == pFast){return NULL;}while (pFast != NULL){pSlow = pSlow->pNext;pFast = pFast->pNext;}return pSlow;
}
功能:找到链表倒数第k个节点
算法原理:
快指针先走k步,慢指针和快指针每次走1步(快指针总是领先慢指针k步),当快指针走到末尾时,慢指针即指向链表倒数第k个节点 。
5、倒置链表
int ReversalLinkList(LinkNode *pHead)
{LinkNode *pTmpNode = NULL;LinkNode *pInsertNode = NULL;pTmpNode = pHead->pNext;pHead->pNext = NULL;pInsertNode = pTmpNode;while (pTmpNode != NULL){pTmpNode = pTmpNode->pNext;pInsertNode->pNext = pHead->pNext;pHead->pNext = pInsertNode;pInsertNode = pTmpNode;}return 0;
}
6、链表的冒泡排序
int BubbleSortLinkList(LinkNode *pHead)
{ LinkNode *pTmpNode1 = NULL;LinkNode *pTmpNode2 = NULL;LinkNode *pEnd = NULL;DataType TmpData;//如果链表没有节点或者只有1个节点返回0 if (NULL == pHead->pNext || NULL == pHead->pNext->pNext){return 0;}while (1){pTmpNode1 = pHead->pNext;pTmpNode2 = pHead->pNext->pNext;if (pTmpNode2 == pEnd){break;}while (pTmpNode2 != pEnd){if (pTmpNode1->Data > pTmpNode2->Data){TmpData = pTmpNode1->Data;pTmpNode1->Data = pTmpNode2->Data;pTmpNode2->Data = TmpData;}pTmpNode1 = pTmpNode1->pNext;pTmpNode2 = pTmpNode2->pNext;}pEnd = pTmpNode1;}return 0;
}
7、链表的选择排序
//选择排序
int SelectSortLinkList(LinkNode *pHead)
{LinkNode *pTmpNode = NULL;LinkNode *pMinNode = NULL;LinkNode *pSwapNode = NULL;DataType TmpData;if (NULL == pHead->pNext){return 0;}pSwapNode = pHead->pNext;while (pSwapNode->pNext != NULL){pMinNode = pSwapNode;pTmpNode = pSwapNode->pNext;while (pTmpNode != NULL){if (pTmpNode->Data < pMinNode->Data){pMinNode = pTmpNode;}pTmpNode = pTmpNode->pNext;}if (pMinNode != pSwapNode){TmpData = pMinNode->Data;pMinNode->Data = pSwapNode->Data;pSwapNode->Data = TmpData;}pSwapNode = pSwapNode->pNext;} return 0;
}