在這里，我把所有關于單鏈表的基本操作，以及面試單鏈表時經常遇到的操作全部實現了一遍（正文分兩大部分，第一部分為單鏈表基本操作，第二部分為面試題）相信大家在面試時只要是問道關于單鏈表的題目，肯定能派上用場哦！好了，廢話不多說，直接上干貨。
#include<assert.h>
#define NULL 0
#include<malloc.h>
#include<stdio.h>
typedef int DataType;
typedef struct Node
{
struct Node*next;
struct Node*random;
DataType data;
}Node, *pNode;
//****************************//
//***單鏈表基本操作****//
//****************************//
void InitList(pNode *pHead);//初始化
pNode BuyNode(DataType data);//構造一個節點
void PushBack(pNode *pHead,DataType data);//尾插
void PopBack(pNode *pHead);//尾刪
void PRintList(pNode pHead);//打印單鏈表
void PushFront(pNode *pHead,DataType data);//頭插
void PopFront(pNode *pHead);//頭刪
pNode Find(pNode pHead,DataType data);//查找
void Insert(pNode pos,DataType data);//任意位置插入結點
void Delete(pNode *pHead,pNode pos);//任意位置刪除結點
void Remove(pNode* pHead,DataType data); //刪除為date節點
void RemoveAll(pNode* pHead,DataType data);//刪除所有為data的結點
size_t size(pNode pHead); //求大小
pNode Front(pNode pHead); //返回尾節點
pNode Back(pNode pHead); //返回頭節點
int Empty(pNode pHead); //判空
void InitList(pNode*pHead) //初始化鏈表
{
assert(pHead);
*pHead = NULL;
}
pNode BuyNode(DataTypedata) //構建一個結點
{
pNode pTemp = (pNode)malloc(sizeof(Node));
if (pTemp)
{
pTemp->data = data;
pTemp->next = NULL;
}
return pTemp;
}
void PushBack(pNode *pHead,DataType data)//尾插，空鏈表和多個結點
{
assert(pHead);
if (NULL == *pHead)
{
*pHead = BuyNode(data);
}
else
{
pNode pCur = *pHead;
while (pCur->next)
{
pCur = pCur->next;
}
pCur->next = BuyNode(data);
}
}
void PopBack(pNode *pHead)//尾刪，不存在、一個結點、多個結點
{
assert(pHead);
if (NULL == *pHead)
{
return;
}
else if (NULL == (*pHead)->next)
{
free(*pHead);
*pHead = NULL;
}
else
{
pNode pCur = *pHead;
pNode pPre = pCur;
while (pCur->next)
{
pPre = pCur;
pCur = pCur->next;
}
free(pCur);
pPre->next = NULL;
}
}
void PrintList(pNodepHead) //打印單鏈表
{
pNode pCur = pHead;
while (pCur)
{
printf("%d->", pCur->data);
pCur = pCur->next;
}
printf("NULL/n");
}
void PushFront(pNode *pHead,DataType data) //頭插
{
assert(pHead);
pNode pNewNode = BuyNode(data);
if (pNewNode)
{
pNewNode->next = *pHead;
*pHead = pNewNode;
}
}
void PopFront(pNode *pHead) //頭刪
{
pNode ps = NULL;
assert(pHead);
if (*pHead ==NULL)
return;
else
{
ps = *pHead;
*pHead = (*pHead)->next;
free(ps);
}
}
pNode Find(pNodepHead, DataTypedata) //查找一個節點
{
assert(pHead);
pNode PcurNode = pHead;
while (PcurNode)
{
if (PcurNode->data == data)
{
return PcurNode;
}
PcurNode = PcurNode->next;
}
return NULL;
}
void Insert(pNodepos, DataTypedata) //任意位置插入節點
{
pNode pNewNode = NULL;
if (NULL ==pos)
return;
pNewNode = BuyNode(data);
pNewNode->next = pos->next;
pos->next = pNewNode;
}
void Delete(pNode *pHead,pNode pos) //任意位置刪除節點
{
assert(*pHead);
if (NULL ==pHead&&NULL ==pos)
return;
if (pos = *pHead)
{
*pHead = pos->next;
free(pos);
}
else
{
pNode pPre = *pHead;
while (pPre->next != pos)
{
pPre = pPre->next;
}
pPre->next = pos->next;
free(pos);
}
}
void Remove(pNode*pHead, DataTypedata) //刪除為data的結點
{
assert(pHead);
Delete(pHead, Find(*pHead,data));
}
void RemoveAll(pNode*pHead, DataTypedata) //刪除所有為data的結點
{
assert(pHead);
pNode pCurNode = NULL;
pNode pPreNode = NULL;
pPreNode = *pHead;
pCurNode = pPreNode->next;
while (pCurNode)
{
if (pCurNode->data = data)
{
pPreNode->next = pCurNode->next;
free(pCurNode);
pCurNode = pPreNode->next;
}
else
{
pCurNode = pCurNode->next;
}
}
if ((*pHead)->data =data)
{
pCurNode = *pHead;
*pHead = (*pHead)->next;
free(pCurNode);
}
}
pNode Back(pNodepHead) //返回尾節點
{
assert(pHead);
pNode pCurNode = pHead;
if (NULL ==pHead)
return NULL;
while (pCurNode->next)
pCurNode = pCurNode->next;
return pCurNode;
}
size_t size(pNodepHead) //求大小
{
pNode pCurNode = pHead;
size_t Count= 0;
while (pCurNode)
{
Count++;
pCurNode = pCurNode->next;
}
return Count;
}
//************鏈表常見面試題****************//
//************鏈表常見面試題****************//
//************鏈表常見面試題****************//
voidPrintListFromTailtoHeda(pNode pHead);//從尾到頭打印單鏈表中的內容
void DelNotTailNode(pNode pos);//刪除一個單鏈表的非尾節電，不能遍歷單鏈表(騰訊筆試題)
void InsertNotHead(pNode pos,DataType data);//在無頭單鏈表的一個非頭結點前插入一個結點
pNode JosephCircle(pNode pHead,size_t M);//單鏈表實現約瑟夫環
pNode Reverse(pNode pHead);//逆制單鏈表(way1)
pNode Reverse_t(pNode pHead);//逆制單鏈表(way2)
void Bubble(pNode pHead);//單鏈表冒泡排序
pNode FindMidNode(pNode pHead);//查找單鏈表中間結點
pNode FindLastKNode(pNode pHead,size_t K);//查找單鏈表倒數第K個結點
void DeleteLastKNode(pNode* pHead,size_t K);//刪除單鏈表倒數第K個結點
pNode Combine(pNode pHead1,pNode pHead2);//合并兩個有序單鏈表
int IsTailCross(pNode pHead1,pNode pHead2);//判斷兩個單鏈表是否相交，
pNode GetTailCross(pNode pHead1,pNode pHead2);//求兩單鏈表相交的交點
pNode HasCircle(pNode pHead);//判斷單鏈表是否帶環
size_t GetCircleLen(pNode pMeetNode);//若單鏈表帶環，則獲取環的長度
pNode GetEnterNode(pNode pHead,pNode pMeetNode);//獲取帶環單鏈表的入口點
intHasCircleWithCircle(pNode pHead1,pNode pHead2);//判斷兩個鏈表是否相交，若相交，求交點（假設鏈表可能帶環）
pNode CopyComplexList(pNode pHead);//拷貝復雜鏈表
///////////////////////////////////////////
voidPrintListFromTailtoHeda(pNodepHead) //從尾到頭打印單鏈表中的內容
{
if (pHead)
{
PrintListFromTailtoHeda(pHead->next);
printf("%d->", pHead->data);
}
}
void DelNotTailNode(pNodepos) //刪除一個單鏈表的非尾節電，不能遍歷單鏈表(騰訊筆試題)
{
pNode pDelNode = NULL;
if (NULL ==pos || NULL ==pos->next)
return;
else
{
pDelNode = pos->next;
pos->next = pDelNode->next;
pos->data = pDelNode->data;
free(pDelNode);
}
}
////
void InsertNotHead(pNodepos, DataTypedata) //在無頭單鏈表的一個非頭結點前插入一個結點
{
pNode pNewNode = NULL;
if (NULL ==pos)
return;
pNewNode = BuyNode(pos->data);
if (pNewNode)
{
pNewNode->next = pos->next;
pos->next = pNewNode;
pos->data = data;
}
}
////
pNode JosephCircle(pNodepHead, size_tM) //單鏈表實現約瑟夫環
{
assert(pHead);
pNode pCurNode = pHead, pDelNode;
if (NULL ==pHead)
return NULL;
while (pCurNode != pCurNode->next)
{ //1.報數
size_t Count = M;
while (--Count)
{
pCurNode= pCurNode->next;
}
//2.刪除結點
pDelNode = pCurNode->next;
pCurNode->data = pDelNode->data;
pCurNode->next = pDelNode->next;
free(pDelNode);
}
return pCurNode;
}
////
pNode Reverse(pNodepHead) //逆制單鏈表(way1)
{
assert(pHead);
pNode pPre = NULL;
pNode pCur = NULL;
pNode pNext = NULL;
if (NULL ==pHead&&NULL ==pHead->next)
return pHead;
pPre = pHead;
pCur = pPre->next;
pNext = pCur->next;
while (pNext)
{
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
pNext = pNext->next;
}
pCur->next = pPre;
pHead->next = NULL;
return pCur;
}
////
pNode Reverse_t(pNodepHead) //逆制單鏈表(way2)
{
assert(pHead);
pNode pPre = NULL;
pNode pCur = NULL;
pNode pNewHead = NULL;
if (NULL ==pHead || NULL ==pHead->next)
return pHead;
pPre = pHead;
pCur = pPre->next;
while (pCur)
{
pPre->next = pNewHead;
pNewHead = pPre;
pPre = pCur;
pCur = pCur->next;
}
pPre->next = pNewHead;
pNewHead = pPre;
return pNewHead;
}
////
void Bubble(pNodepHead) //單鏈表冒泡排序
{
assert(pHead);
pNode pPre = NULL;
pNode pCur = NULL;
pNode pTail = NULL;
int flag = 1;
if (NULL ==pHead || NULL ==pHead->next)
return;
while (pHead != pTail)
{
flag = 1;
pPre = pHead;
pCur = pPre->next;
while (pCur != pTail)
{
if (pPre->data > pCur->data)
{
DataType temp = pPre->data;
pPre->data = pCur->data;
pCur->data = temp;
flag= 0;
}
pPre = pCur;
pCur = pCur->next;
}
pTail = pPre;
if (flag)
return;
}
}
////
pNode FindMidNode(pNodepHead)
{
pNode pSlow = pHead;
pNode pFast = pHead;
while (pFast && pFast->next)//結點偶數個Fast先空，結點計數個，Fast->next先空；
{
pSlow = pSlow->next;
pFast = pFast->next->next;
}
return pSlow;//返回后一個結點，（結點為偶數個，則中間結點有兩個）
}
pNode FindLastKNode(pNodepHead, size_tK)
{
assert(pHead);
pNode pFast = pHead;
pNode pSlow = pHead;
if (NULL ==pHead || 0 == K)
return NULL;
while (K--)
{
if (NULL == pFast)
return NULL;
pFast = pFast->next;
}
while (pFast)
{
pFast = pFast->next;
pSlow = pSlow->next;
}
return pSlow;
}
////
pNode Combine(pNodepHead1, pNodepHead2)
{
pNode p1 = pHead1;
pNode p2 = pHead2;
pNode pNewHead = NULL;
pNode pTailNode = NULL;
if (NULL ==pHead1)
return pHead2;
if (NULL ==pHead2)
return pHead1;
if (p1->data < p2->data)
{
pNewHead = p1;
p1 = p1->next;
pTailNode = p1;
}
else
{
pNewHead = p2;
p2 = p2->next;
pTailNode = p2;
}
while (p1&&p2)
{
if (p1->data < p2->data)
{
pTailNode->next = p1;
p1 = p1->next;
}
else
{
pTailNode->next = p2;
p2 = p2->next;
}
pTailNode = pTailNode->next;
}
if (p1)
pTailNode->next = p1;
if (p2)
pTailNode->next = p2;
return pNewHead;
}
/////
int IsTailCross(pNodepHead1, pNodepHead2)
{
pNode pTailNode1 = pHead1;
pNode pTailNode2 = pHead2;
if (NULL ==pHead1 || NULL ==pHead2)
return 0;
while (pTailNode1->next)
{
pTailNode1 = pTailNode1->next;
}
while (pTailNode2->next)
{
pTailNode2 = pTailNode2->next;
}
if (pTailNode1 == pTailNode2)
return 1;
return 0;
}
/////
pNode GetTailCross(pNodepHead1, pNodepHead2)
{
size_t Count1 = 0;
size_t Count2 = 0;
int Gap = 0;
pNode pL1 = pHead1;
pNode pL2 = pHead2;
if (0==(IsTailCross(pHead1,pHead2)))
return NULL;
Count1 = size(pHead1);
Count2 = size(pHead2);
Gap = Count1 - Count2;
if (Gap > 0)
{
while (Gap--)
pL1=pL1->next;
}
else
{
while (Gap++)
pL2 = pL2->next;
}
while (pL1 != pL2)
{
pL1 = pL1->next;
pL2 = pL2->next;
}
return pL1;
}
/////
pNode HasCircle(pNodepHead)
{
assert(pHead);
pNode pFast = pHead;
pNode pSlow = pHead;
while (pFast &&pFast->next)
{
pFast = pFast->next->next;
pSlow = pSlow->next;
if (pFast == pSlow)
return pFast;
}
return NULL;
}
////
size_t GetCircleLen(pNodepMeetNode)
{
pNode pCurNode = pMeetNode;
size_t Count = 1;
if (NULL ==pMeetNode)
return 0;
while (pCurNode->next != pMeetNode)
{
Count++;
pCurNode = pCurNode->next;
}
return Count;
}
////
pNode GetEnterNode(pNodepHead, pNodepMeetNode)
{
pNode pM = pHead;
pNode pN = pMeetNode;
if (NULL ==pHead || NULL ==pMeetNode)
return NULL;
while (pM != pN)
{
pM = pM->next;
pN =pN->next;
}
return pM;
}
////
intHasCircleWithCircle(pNodepHead1, pNodepHead2)
{
pNode pL1 = pHead1;
pNode pL2 = pHead2;
pNode pMeetNode1 = HasCircle(pHead1);
pNode pMeetNode2 = HasCircle(pHead2);
if (NULL == pMeetNode1&&NULL == pMeetNode2)
{
while (pL1->next)
{
pL1 = pL1->next;
}
while (pL2->next)
{
pL2 = pL2->next;
}
if (pL1 == pL2)
return 1;
}
else if (pMeetNode1&&pMeetNode2)
{
pNode pCurNode = pMeetNode1;
while (pCurNode->next != pMeetNode1)
{
if (pCurNode = pMeetNode2)
return 2;
pCurNode = pCurNode->next;
}
if (pCurNode = pMeetNode2)
return 2;
}
return 0;
}
//////
pNode CopyComplexList(pNodepHead)
{
pNode p1 = pHead;
pNode p2 = NULL;
pNode pNewNode = NULL;
if (NULL ==pHead)
return NULL;
while (p1)//1、插入結點
{
pNewNode = BuyNode(p1->data);
assert(pNewNode);
pNewNode->next = p1->next;
p1->next = pNewNode;
p1 = p1->next->next;
}
p1 = pHead;
p2 = p1->next;
while (p2->next)//2、隨機域賦值
{
if (NULL == p1->random)
p2->random = NULL;
else
p2->random = p1->random->next;
p1 = p2->next;
p2 = p1->next;
}
if (p1->random)
p2->random = p1->random->next;
else
p2->random = NULL;
p1 = pHead;
p2 = p1->next;
pNewNode = p2;
while (p2->next)//3、拆分鏈表
{
p1->next = p2->next;
p2->next = p1->next->next;
p1 = p1->next;
p2 = p2->next;
}
p2->next = NULL;
return pNewNode;
}
//////////////////////////////////////////////
//////////////////////////////////////////////
新聞熱點
疑難解答
