1欲诺、鏈表的結構
typedef int Data;
struct ListNode {
Date data;
ListNode *pNext;
};
2抄谐、鏈表的逆序
ListNode *reverseList(ListNode *pHead)
{
ListNode *pReversedHead = NULL;
ListNode *pNode = pHead;
ListNode *pPrev = NULL;
while (pNode != NULL) {
ListNode *pNext = pNode->pNext;
if (pNext == NULL)
pReversedHead = pNode;
pNode->pNext = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
3、找出倒數(shù)第k個
ListNode* findKthToTail(ListNode* pListHead, unsigned int k)
{
if (pListHead == NULL || k == 0)
return NULL;
ListNode *pAhead = pListHead;
ListNode *pBehind = NULL;
for (unsigned int i = 0; i < k - 1; i++) {
if (pAhead->pNext != NULL)
pAhead = pAhead->pNext;
else
return NULL;
}
pBehind = pListHead;
while (pAhead->pNext != NULL) {
pAhead = pAhead->pNext;
pBehind = pBehind->pNext
}
return pBehind;
}
4扰法、找出中間元素
ListNode *getMiddleNode(ListNode *pNode)
{
ListNode *firstNode = pNode;
ListNode *backNode = pNode;
while (firstNode != NULL) {
firstNode = firstNode->pNext->pNext;
backNode = backNode->pNext;
}
return backNode;
}
5蛹含、判斷鏈表是否有環(huán)
bool judgeListCricle(ListNode *pNode)
{
if (pNode == NULL)
return false;
ListNode *first = pNode;
ListNode *back = pNode;
while(firt->pNext!=NULL && back->pNext->pNext!=NULL) {
first = first->pNext;
back = back->pNext->pNext;
if (first == back)
return ture;
}
return false;
}
