這篇博客只有針對單鏈表的不同面試題的不同函數(shù)，沒有對單鏈表的具體實(shí)現(xiàn)方法的介紹。
單鏈表的具體實(shí)現(xiàn)方法（創(chuàng)建，初始化，前插，后插，刪除，插入，銷毀等），可以參考我的另一邊博客：
http://blog.csdn.net/ljx_5489464/article/details/50893430

以下是單鏈表面試題的具體實(shí)現(xiàn)：

1、從尾到頭打印單鏈表

void PrintListTailToHead(PSListNode pHead) {if (NULL != pHead){//遞歸實(shí)現(xiàn)PrintListTailToHead(pHead->pNextNode);printf("%d ", pHead->data);} }

2、刪除一個無頭單鏈表的非尾節(jié)點(diǎn)

void DelNotTailNode(PSListNode pos) {PSListNode pNode = NULL;assert(pos);if (NULL == pos->pNextNode){return;}else{DataType temp = 0;//交換pos和pos->pNextNode的數(shù)據(jù)（相當(dāng)于交換了兩個結(jié)點(diǎn)的位置），使問題轉(zhuǎn)換為刪除pos指向的結(jié)點(diǎn)的下一個結(jié)點(diǎn)temp = pos->data;pos->data = pos->pNextNode->data;pos->pNextNode->data = temp;pNode = pos->pNextNode;pos->pNextNode = pos->pNextNode->pNextNode;free(pNode);pNode = NULL;} }

3、在無頭單鏈表的一個非頭節(jié)點(diǎn)前插入一個節(jié)點(diǎn)

void InsertNotHead(PSListNode pos, DataType data) {if (NULL == pos){return;}else{PSListNode pNewNode = ByeNode(data);if (NULL == pNewNode){printf("開辟結(jié)點(diǎn)空間失敗!\n");return;}else{//交換pos和pNewNode的數(shù)據(jù)（相當(dāng)于交換了兩個結(jié)點(diǎn)的位置），使問題轉(zhuǎn)換為在pos指向的結(jié)點(diǎn)的下一個結(jié)點(diǎn)處插入新結(jié)點(diǎn)pNewNode->data = pos->data;pos->data = data;pNewNode->pNextNode = pos->pNextNode;pos->pNextNode = pNewNode;}} }

4、單鏈表實(shí)現(xiàn)約瑟夫環(huán)(JosephCircle)

//使鏈表形成一個環(huán) void FormCyc(PSListNode *pHead) {if (NULL == pHead){return;}else{PSListNode pNode = *pHead;while (NULL != (pNode->pNextNode)){pNode = pNode->pNextNode;}pNode->pNextNode = *pHead;} }PSListNode JosephCircle(PSListNode pHead, int M) {if ((NULL == pHead) || (M <= 0)){return NULL;}else{//讓鏈表中所有元素形成一個環(huán)FormCyc(&pHead);PSListNode pPreNode = NULL;PSListNode pCurNode = pHead;PSListNode pDesNode = NULL;int temp = M;while (pCurNode->pNextNode != pCurNode){temp = M;pPreNode = pCurNode;while (--temp){pPreNode = pCurNode;pCurNode = pCurNode->pNextNode;}//記住要從鏈表中刪除的節(jié)點(diǎn)的位置，把它的空間釋放了pDesNode = pCurNode;pCurNode = pCurNode->pNextNode;pPreNode->pNextNode = pCurNode;free(pDesNode);pDesNode = NULL;}//如果M=1，就說明所有結(jié)點(diǎn)都要被刪除，那么就返回空，否則就返回剩下的那個結(jié)點(diǎn)的指針if (1 == M){free(pCurNode);pCurNode = NULL;}else{pCurNode->pNextNode = NULL;}return pCurNode;} }

5、逆置/反轉(zhuǎn)單鏈表

逆置鏈表：方法一：前插法 //void ReverseList(PSListNode* pHead) //{ // if (NULL == *pHead) // { // return; // } // else // { // //創(chuàng)建一個新的空鏈表，遍歷pHead指向的鏈表里的所有節(jié)點(diǎn)，每找到一個，就前插到新鏈表里 // PSListNode pNewHead = *pHead; // *pHead = (*pHead)->pNextNode; // //第一次前插到新鏈表里的結(jié)點(diǎn)，是新鏈表的尾節(jié)點(diǎn)，所以要使它的下一個結(jié)點(diǎn)為空 // pNewHead->pNextNode = NULL; // while (NULL != *pHead) // { // PSListNode pNode = *pHead; // *pHead = (*pHead)->pNextNode; // pNode->pNextNode = pNewHead; // pNewHead = pNode; // } // *pHead = pNewHead; // } //} //逆置鏈表：方法二：三指針法 void ReverseList(PSListNode* pHead) {assert(pHead);if ((*pHead == NULL) || ((*pHead)->pNextNode) == NULL){return;}else{PSListNode pPreNode = *pHead;PSListNode pCurNode = (*pHead)->pNextNode;PSListNode pOffNode = (*pHead)->pNextNode->pNextNode;PSListNode pNode = NULL;while (1){pCurNode->pNextNode = pPreNode;pPreNode->pNextNode = pNode;pNode = pPreNode;if (pOffNode == NULL){break;}else{pPreNode = pCurNode;pCurNode = pOffNode;pOffNode = pOffNode->pNextNode;}}*pHead = pCurNode;} }

6、單鏈表排序（冒泡排序）

void SortList(PSListNode pHead) {if (NULL == pHead){return;}else{int flag = 0;PSListNode pTailNode = NULL;//當(dāng)設(shè)置的尾節(jié)點(diǎn)與頭結(jié)點(diǎn)指向同一個節(jié)點(diǎn)時，說明只有一個元素為排序，那么冒泡完成while (pTailNode != pHead){PSListNode pPreNode = pHead;//每次參與比較的都是尾節(jié)點(diǎn)前面的結(jié)點(diǎn)while (pPreNode->pNextNode != pTailNode){PSListNode pCurNode = pPreNode->pNextNode;if (pPreNode->data > pCurNode->data){DataType dTemp = pPreNode->data;pPreNode->data = pCurNode->data;pCurNode->data = dTemp;flag = 1;}pPreNode = pPreNode->pNextNode;}//對冒泡的優(yōu)化，只要有一趟比較沒有發(fā)生結(jié)點(diǎn)交換，說明冒泡完成，就可以退出冒泡的代碼塊了if (0 == flag){break;}pTailNode = pPreNode;}} }

7、合并兩個有序鏈表,合并后依然有序

PSListNode MergeList(PSListNode pL1, PSListNode pL2) {PSListNode pNewNode = NULL;PSListNode pListNode1 = pL1;PSListNode pListNode2 = pL2;PSListNode pNode = NULL;if (NULL == pListNode1){return pListNode2;}else if (NULL == pListNode2){return pListNode1;}else{//先把新鏈表的頭結(jié)點(diǎn)的指針找到,每次取兩個鏈表中保存的數(shù)據(jù)較小的結(jié)點(diǎn)后插到新鏈表中if (pListNode1->data > pListNode2->data){pNode = pListNode2;pListNode2 = pListNode2->pNextNode;pNewNode = pNode;}else{pNode = pListNode1;pListNode1 = pListNode1->pNextNode;pNewNode = pNode;}while ((NULL != pListNode1) && (NULL != pListNode2)){if (pListNode1->data > pListNode2->data){pNode->pNextNode = pListNode2;pListNode2 = pListNode2->pNextNode;pNode = pNode->pNextNode;}else{pNode->pNextNode = pListNode1;pListNode1 = pListNode1->pNextNode;pNode = pNode->pNextNode;}}if (NULL == pListNode1){pNode->pNextNode = pListNode2;return pNewNode;}else{pNode->pNextNode = pListNode1;return pNewNode;}} }

8、查找單鏈表的中間節(jié)點(diǎn)，要求只能遍歷一次鏈表

PSListNode FindMidNode(PSListNode pHead) {if (NULL == pHead){return NULL;}else{//快慢指針PSListNode pSlow = pHead;PSListNode pFast = pHead;//注意結(jié)束條件得加上NULL != pFast->pNextNode，否則當(dāng)NULL == pFast->pNextNode時，進(jìn)入循環(huán)，//執(zhí)行pFast = pFast->pNextNode->pNextNode時會崩潰while ((NULL != pFast) && (NULL != pFast->pNextNode)){pSlow = pSlow->pNextNode;pFast = pFast->pNextNode->pNextNode;}return pSlow;} }

9、查找單鏈表的倒數(shù)第k個節(jié)點(diǎn)，要求只能遍歷一次鏈表

PSListNode FindLastKNode(PSListNode pHead, int K) {if ((NULL == pHead) || (K <= 0)){return NULL;}else{PSListNode pFast = pHead;PSListNode pSlow = pHead;//利用快慢指針，讓快指針先走K-1步，然后兩指針同時走，直到快指針指向的下一個結(jié)點(diǎn)為空為止while (--K){pFast = pFast->pNextNode;if (NULL == pFast){return NULL;}}while (NULL != pFast->pNextNode){pFast = pFast->pNextNode;pSlow = pSlow->pNextNode;}return pSlow;} }

10、判斷單鏈表是否帶環(huán)？若帶環(huán)，求環(huán)的長度？求環(huán)的入口點(diǎn)？

PSListNode HasCycle(PSListNode pHead) {if ((NULL == pHead) || (NULL == pHead->pNextNode)){return NULL;}else{PSListNode pFast = pHead->pNextNode->pNextNode;PSListNode pSlow = pHead->pNextNode;//利用快慢指針，讓快指針每次走兩步，慢指針每次走一步，要是快指針沒有走到NULL，且快指針與慢指針指向相同就說明是有環(huán)while (pFast != pSlow){//快指針要是沒有指向?yàn)榭?#xff0c;那么慢指針就不可能指向空（快指針走得快）if (NULL == pFast){return;}else{pFast = pFast->pNextNode;pSlow = pSlow->pNextNode; if (NULL == pFast){return;}else{pFast = pFast->pNextNode;}}}return pFast;} }int GetCyleLen(PSListNode pMeetNode) {//默認(rèn)傳的參數(shù)是HasCycle函數(shù)返回的環(huán)中的一個結(jié)點(diǎn)if (NULL == pMeetNode){return 0;}else{int nCount = 1;PSListNode pNode = pMeetNode;while (pMeetNode != pNode->pNextNode){pNode = pNode->pNextNode;nCount++;}return nCount;} } //pMeetNode參數(shù)是用HasCycle函數(shù)求鏈表是否有環(huán)時pFast指針與pSlow指針的碰撞點(diǎn) //定律：在鏈表頭，pFast指針與pSlow指針的碰撞點(diǎn)分別設(shè)定一個指針，每次各走一步，兩個指針必定相遇，則相遇第一點(diǎn)為環(huán)入口點(diǎn) PSListNode FindEnterNode(PSListNode pHead, PSListNode pMeetNode) {PSListNode pNode = pHead;if ((NULL == pHead) || (NULL == pMeetNode)){return NULL;}while (pNode != pMeetNode){pNode = pNode->pNextNode;pMeetNode = pMeetNode->pNextNode;}return pNode; }

11、判斷兩個鏈表是否相交，若相交，求交點(diǎn)。（假設(shè)鏈表不帶環(huán)）

int IsListCrose(PSListNode pL1, PSListNode pL2) {if ((NULL == pL1) || (NULL == pL2)){return 0;}else{PSListNode PSList1 = pL1;PSListNode PSList2 = pL2;while (NULL != PSList1->pNextNode){PSList1 = PSList1->pNextNode;}while (NULL != PSList2->pNextNode){PSList2 = PSList2->pNextNode;}//不帶環(huán)的兩個鏈表相交，那么它們的最后一個結(jié)點(diǎn)的指針的值一定是相等的if (PSList1 == PSList2){return 1;}else{return 0;}} }

12、判斷兩個鏈表是否相交，若相交，求交點(diǎn)。（假設(shè)鏈表可能帶環(huán)）【升級版】

int IsListCroseWithCycle(PSListNode pL1, PSListNode pL2) {PSListNode pMeetNode1 = HasCycle(pL1);PSListNode pMeetNode2 = HasCycle(pL2);if ((NULL == pL1) || (NULL == pL2)){return 0;}//兩個鏈表都沒環(huán)的情況else if ((NULL == pMeetNode1) && (NULL==pMeetNode2)){PSListNode PSList1 = pL1;PSListNode PSList2 = pL2;while (NULL != PSList1->pNextNode){PSList1 = PSList1->pNextNode;}while (NULL != PSList2->pNextNode){PSList2 = PSList2->pNextNode;}//不帶環(huán)的兩個鏈表相交，那么它們的最后一個結(jié)點(diǎn)的指針的值一定是相等的if (PSList1 == PSList2){return 1;}else{return 0;}}// 兩個鏈表都有環(huán)的情況(這種情況肯定是兩個鏈表共用一個環(huán))else if ((NULL != pMeetNode1) && (NULL != pMeetNode2)){while (pMeetNode1->pNextNode != pMeetNode1){//找到一個鏈表中處于環(huán)中的點(diǎn)，遍歷另一個鏈表中環(huán)中的點(diǎn)，看他們是否會出現(xiàn)相等的情況，出現(xiàn)，則可能相交if (pMeetNode1 == pMeetNode2){return 1;}pMeetNode1 = pMeetNode1->pNextNode;}//跳出循環(huán)時，遍歷的組后一個結(jié)點(diǎn)還沒進(jìn)行比較，此處處理這種情況if (pMeetNode1 == pMeetNode2){return 1;}else{return 0;}}// 一個鏈表有環(huán)，一個沒環(huán)，這種情況不會相交else{return 0;} }

13、求鏈表相交時的交點(diǎn)

//鏈表相交時的交點(diǎn) PSListNode IntersectionNode(PSListNode pL1, PSListNode pL2) {int count1 = 0;int count2 = 0;PSListNode PSList1 = pL1;PSListNode PSList2 = pL2;PSListNode pMeetNode1 = HasCycle(pL1);PSListNode pMeetNode2 = HasCycle(pL2);if ((NULL == pL1) || (NULL == pL2)){return NULL;}else{//先求每個鏈表的長度//兩個鏈表都沒環(huán)if ((NULL == pMeetNode1) && (NULL == pMeetNode2)){while (NULL != PSList1){PSList1 = PSList1->pNextNode;count1++;}while (NULL != PSList2){PSList2 = PSList2->pNextNode;count2++;}}//兩個鏈表都有環(huán)else if ((NULL != pMeetNode1) && (NULL != pMeetNode2)){PSListNode pInNode1 = FindEnterNode(PSList1, pMeetNode1);PSListNode pInNode2 = FindEnterNode(PSList2, pMeetNode2);//先計(jì)算頭指針到環(huán)入口結(jié)點(diǎn)的長度，再計(jì)算環(huán)的長度while (PSList1 != pInNode1){PSList1 = PSList1->pNextNode;count1++;}while (PSList1->pNextNode != PSList1){PSList1 = PSList1->pNextNode;count1++;}count1++;;while (PSList2 != pInNode2){PSList2 = PSList2->pNextNode;count2++;}while (PSList2->pNextNode != PSList1){PSList2 = PSList2->pNextNode;count2++;}count2++;;}//一個有環(huán)，一個沒環(huán)，不會相交else{return NULL;}//讓長度長的鏈表的頭指針先走它長于另一個鏈表的結(jié)點(diǎn)數(shù)//在計(jì)算鏈表長度時修改了這兩個指針的值，在這兒需要把它們改回來PSList1 = pL1;PSList2 = pL2;if (count1 > count2){int temp = count1 - count2;while (0 == temp--){PSList1 = PSList1->pNextNode;}}else{int temp = count2 - count1;while (0 == temp--){PSList2 = PSList2->pNextNode;}}//此時，讓兩個鏈表的頭指針同時移動，直到它們相等就找到了交點(diǎn)//因?yàn)轭}目是找交點(diǎn)，那么交點(diǎn)就存在，所以這兒不用怕死循環(huán)while (1){if (PSList1 = PSList2){break;}PSList1 = PSList1->pNextNode;PSList2 = PSList2->pNextNode;}return PSList1;} }

14、求兩個已排序單鏈表中相同的數(shù)據(jù)。void UnionSet(Node* l1, Node* l2);

PSListNode ByeNode(DataType data) {PSListNode pNewNode = (PSListNode)malloc(sizeof(struct SListNode));if (NULL != pNewNode){pNewNode->data = data;//注意使開辟的新節(jié)點(diǎn)的指向?yàn)榭?/span>pNewNode->pNextNode = NULL;}return pNewNode; }PSListNode UnionSet(PSListNode pL1, PSListNode pL2) {PSListNode PSList1 = pL1;PSListNode PSList2 = pL2;PSListNode pNewHead = NULL;PSListNode pNode = NULL;//每次比較兩個鏈表頭指針指向的數(shù)據(jù)是否相等，不相等，就讓數(shù)據(jù)小的頭指針后移，相等，則把該數(shù)據(jù)保存起來，//兩個頭指針同時后移，直到其中一個指向空為止while ((NULL == PSList1) || (NULL == PSList2)){if (PSList1->data > PSList2->data){PSList2 = PSList2->pNextNode;}else if (PSList1->data < PSList2->data){PSList1 = PSList1->pNextNode;}//用一個新的鏈表來保存兩個鏈表中相同的數(shù)據(jù)else{if (pNewHead == NULL){pNewHead = ByeNode(PSList1->data);pNode = pNewHead;PSList1 = PSList1->pNextNode;PSList2 = PSList2->pNextNode;}else{pNode = pNode->pNextNode;pNode = ByeNode(PSList1->data);PSList1 = PSList1->pNextNode;PSList2 = PSList2->pNextNode;}}}return pNewHead; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的C语言实现单链表面试题汇总的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。