常見的連結清單面試題大彙總：

源代碼下載下傳連結

1，建立一個連結清單結點

2，周遊連結清單中的所有結點

3，倒序列印連結清單

4，往連結清單末尾添加結點

5，往連結清單前端添加結點,

6，擷取連結清單的節點數目

7，銷毀連結清單

8，求連結清單中倒數第K個節點

9，反轉連結清單

10，查找連結清單中間節點

11，判斷連結清單是否有環

12，判斷連結清單是否有環，并傳回環上的節點數目

13，判斷連結清單是否有環，并傳回環上的入口節點

14，兩個連結清單中的第一個公共節點

15，合并兩個有序連結清單,

16，用O(1)的時間複雜度删除單連結清單中的某個節點

17，連結清單的排序–采用選擇排序算法實作複雜度n^2

18，連結清單的排序–采用歸并排序算法實作複雜度log(n)

19，連結清單中結點去重

20，給定連結清單中間某個節點，将待插入節點插入給定節點之前

#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace  std;

//連結清單結構 C語言結構
typedef struct ListNode
{
    int m_nValue;
    struct ListNode* m_pNext;
}ListNode;

//連結清單結構 C++語言結構
struct ListNodeCpp
{
    int m_nValue;
    ListNodeCpp * m_pNext;

    ListNodeCpp():m_nValue(),m_pNext(NULL){}
    ListNodeCpp(int value):m_nValue(value),m_pNext(NULL){}
};

/*
建立一個連結清單結點
*/
ListNode* CreateListNode(int value)
{
    ListNode *pNode = new ListNode;
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;

    return pNode;

}

/*
周遊連結清單中的所有結點
*/
void PrintList(ListNode* pHead)
{
    ListNode *pNode = pHead;

    while(pNode != NULL)
    {
        cout<<pNode->m_nValue<<" ";
        pNode = pNode->m_pNext;
    }
    cout<<endl;
}

/*
倒序列印連結清單
*/

void PrintListReverse(ListNode* pHead)
{
    if (pHead == NULL)
    {
        return ;
    }
    PrintListReverse(pHead->m_pNext);

    cout<<pHead->m_nValue<<ends;
}


/*
往連結清單末尾添加結點

注意這裡pHead是一個指向指針的指針，在主函數中一般傳遞的是引用。
因為如果要為連結清單添加結點，那麼就會修改連結清單結構，是以必須傳遞引用才能夠儲存修改後的結構。
*/
void AddToTail(ListNode* & pHead,int value)
{
    ListNode* pNew = new ListNode();//新插入的結點
    pNew->m_nValue = value;
    pNew->m_pNext = NULL;

    if(pHead == NULL)//空連結清單
    {
        pHead = pNew;
    }
    else
    {
        ListNode* pNode = pHead;

        while(pNode->m_pNext!=NULL)
            pNode=pNode->m_pNext;

        pNode->m_pNext=pNew;
    }

}

/*
往連結清單前端添加結點

*/

void AddToHead(ListNode* & pHead,int value)
{
    ListNode *pNew = new ListNode;
    pNew->m_nValue = value;
    pNew->m_pNext = pHead;

    pHead = pNew;
}


/*
擷取連結清單的節點數目
*/
int GetListLength(ListNode *pHead)
{
    int len =;
    ListNode *pNode = pHead;

    while(pNode != NULL)
    {
        len ++;
        pNode = pNode->m_pNext;
    }

    return len;
}

/*
銷毀連結清單
*/
void ReleaseList(ListNode *&pHead)
{
    ListNode *pNode = pHead;
    ListNode *pNext;

    while(pNode != NULL)
    {
        pNext = pNode->m_pNext;
        delete pNode;

        pNode = pNext;
    }

    pHead = NULL;
}

/*
求連結清單中倒數第K個節點
設定快慢指針，快指針超前慢指針k-1個節點，然後快慢指針再同時周遊連結清單，
當快指針周遊到連結清單結尾時，慢指針是倒數第k個節點。
*/
ListNode * FindKthToTail(ListNode *pHead,int k)
{
    if (pHead == NULL || k <=  )
    {
        return NULL;
    }

    ListNode *p1,*p2;
    p1 = pHead;
    p2 = pHead;

    for (int i = ; i < k - ; i ++)
    {
        if (p1 == NULL)
        {
            return NULL;
        }
        p1 = p1->m_pNext;
    }

    while (p1->m_pNext != NULL)
    {
        p1 = p1->m_pNext;
        p2 =  p2->m_pNext;
    }

    return p2;
}

/*
反轉連結清單
*/
ListNode * ReverseList(ListNode *&pHead)
{
    if (pHead == NULL  || pHead->m_pNext == NULL)
    {
        return pHead;
    }

    ListNode* pReverseHead = NULL;
    ListNode* pNode = pHead;
    ListNode* pPrev = NULL;


    while(pNode != NULL)
    {
        ListNode *pNext = pNode->m_pNext;

        if (pNext == NULL)
        {
            pReverseHead = pNode;
        }

        pNode->m_pNext = pPrev;

        pPrev = pNode;
        pNode = pNext;
    }

    pHead = pReverseHead;

    return pReverseHead;
}


/*
查找連結清單中間節點

查找連結清單中間節點，設定快慢指針，快指針一次走兩步，慢指針一次走一步
*/

ListNode *SearchMidNode( ListNode *pHead)
{
    if ( pHead == NULL  )
        return NULL;

    ListNode *pFast = pHead;
    ListNode *pSlow = pHead;

    //若節點為N個， N為奇數，則傳回第N/2 +1個節點， N為偶數，則傳回第N/2個節點
    while( pFast->m_pNext  != NULL && 
        pFast->m_pNext->m_pNext != NULL)
    {
        pFast = pFast->m_pNext->m_pNext;
        pSlow = pSlow->m_pNext;
    }

    return pSlow;
}

/*
判斷連結清單是否有環
使用兩個指針，快指針一次走兩個節點，慢指針一次走一個節點，相遇則表示有環，否則無環。
*/

bool CheckCircle(ListNode *pHead)
{
    if (pHead == NULL)
    {
        return false;
    }


    ListNode *pFast = pHead;
    ListNode *pSlow = pHead;

    while( pFast->m_pNext  != NULL && 
        pFast->m_pNext->m_pNext != NULL)
    {
        pFast = pFast->m_pNext->m_pNext;
        pSlow = pSlow->m_pNext;

        if (pFast == pSlow)
        {
            return true;
        }

    }

    return false;
}

/*
判斷連結清單是否有環，并傳回環上的節點數目
*/

int GetCircleNodeNum(ListNode *pHead)
{
    if (pHead == NULL)
    {
        return ;
    }


    ListNode *pFast = pHead;
    ListNode *pSlow = pHead;

    while( pFast->m_pNext  != NULL && 
        pFast->m_pNext->m_pNext != NULL)
    {
        pFast = pFast->m_pNext->m_pNext;
        pSlow = pSlow->m_pNext;

        if (pFast == pSlow)
        {

            int num = ; 
            pFast = pFast->m_pNext;

            while (pFast != pSlow)
            {
                num ++;
                pFast = pFast->m_pNext;
            }

            return num;
        }

    }

    return ;
}


/*
判斷連結清單是否有環，并傳回環上的入口節點
首先擷取換上節點的資料K，然後使用間隔K的兩個指針，相遇的時候 即為入口
*/

ListNode *GetEnterNodeOfCircle(ListNode *pHead)
{
    if (pHead == NULL)
    {
        return NULL;
    }

    int len = GetCircleNodeNum(pHead);
    if (len == )
    {
        return NULL;
    }

    ListNode* p1 = pHead;
    ListNode* p2 = pHead;

    for (int i = ;i < len ; i ++)
    {
        if (p1->m_pNext != NULL)
        {
            p1 = p1->m_pNext;
        }
    }

    while (p1 != p2)
    {
        p1 = p1->m_pNext;
        p2 = p2->m_pNext;
    }

    return p1;
}



/*
兩個連結清單中的第一個公共節點

首先周遊兩個連結清單得到它們的長度，就能知道哪個連結清單比較長，以及長的連結清單比短
的連結清單多幾個節點。在第二次周遊的時候，先在較長的節點上走若幹步，接着同時
在兩個連結清單上周遊，找到的第一個相同的節點就是它們的公共的節點。
*/


ListNode* FindFirstCommonNode(ListNode* pHead1,ListNode *pHead2)
{
    //得到兩個連結清單的長度
    unsigned int nLength1 = GetListLength(pHead1);
    unsigned int nLength2 = GetListLength(pHead2);

    int nLengthDif = nLength1 - nLength2;

    ListNode *pHeadLong = pHead1;
    ListNode *pHeadShort = pHead2;

    if(nLength2 > nLength1 )
    {
        ListNode *pHeadLong = pHead2;
        ListNode *pHeadShort = pHead1;

        nLengthDif = nLength2 - nLength1;

    }

    //先在長連結清單上走幾步，再同時在兩個連結清單上周遊。
    for(int i = ;i < nLengthDif;i++)
        pHeadLong = pHeadLong->m_pNext;

    while((pHeadLong != NULL)&&(pHeadShort != NULL)
        &&(pHeadLong != pHeadShort ))
    {

        pHeadLong = pHeadLong->m_pNext;
        pHeadShort = pHeadShort->m_pNext;

    }
    //得到第一個公共節點
    ListNode *pFirstCommonNode =    pHeadLong ;

    return pFirstCommonNode;
}


/*
合并兩個有序連結清單,
非遞歸方法  
*/

ListNode *MergeTwoList(ListNode *pListOneHead, ListNode *pListTwoHead)  
{  
    if (pListOneHead == NULL)  
    {  
        return pListTwoHead;  
    }  

    if (pListTwoHead == NULL)  
    {  
        return pListOneHead;  
    }  

    ListNode *pNode1 = pListOneHead;  
    ListNode *pNode2 = pListTwoHead;  
    ListNode *pMergeListHead = NULL;  
    ListNode *pCurLastNode = NULL;  

    if (pNode1->m_nValue < pNode2->m_nValue)  
    {             
        pMergeListHead = pListOneHead;  
        pNode1 = pNode1->m_pNext;  
        pCurLastNode = pMergeListHead;  
    }  
    else  
    {  
        pMergeListHead = pListTwoHead;  
        pNode2 = pNode2->m_pNext;  
        pCurLastNode = pMergeListHead;  
    }  

    while (pNode1 != NULL && pNode2 != NULL)  
    {  
        if (pNode1->m_nValue < pNode2->m_nValue)  
        {     
            pCurLastNode->m_pNext = pNode1;  
            pCurLastNode = pNode1;  
            pNode1 = pNode1->m_pNext;              
        }  
        else  
        {  
            pCurLastNode->m_pNext = pNode2;  
            pCurLastNode = pNode2;  
            pNode2 = pNode2->m_pNext;              
        }  

        if (pNode1 == NULL)  
        {  
            pCurLastNode->m_pNext = pNode2;                
        }  

        if (pNode2 == NULL)  
        {  
            pCurLastNode->m_pNext = pNode1;            
        }  
    }  

    return pMergeListHead;  
}  


/*
用O(1)的時間複雜度删除單連結清單中的某個節點

一般單連結清單删除某個節點，需要知道删除節點的前一個節點，則需要O(n)的周遊時間，
顯然正常思路是不行的。在仔細看題目，換一種思路，既然不能在O(1)得到删除節點的
前一個元素，但我們可以輕松得到後一個元素，這樣，我們何不把後一個元素指派給待
删除節點，這樣也就相當于是删除了目前元素。可見，該方法可行，但如果待删除節點
為最後一個節點，則不能按照以上思路，沒有辦法，隻能按照正常方法周遊，時間複雜
度為O(n)，是不是不符合題目要求呢？可能很多人在這就會懷疑自己的思考，進而放
棄這種思路，最後可能放棄這道題，這就是這道面試題有意思的地方，雖看簡單，但是
考察了大家的分析判斷能力，是否擁有強大的心理，充分自信。其實我們分析一下，仍然
是滿足題目要求的，如果删除節點為前面的n-1個節點，則時間複雜度為O(1)，隻有删除
節點為最後一個時，時間複雜度才為O(n)，是以平均的時間複雜度為：
（O(1) * (n-1) + O(n)）/n = O(1);仍然為O(1).
*/

void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
{
    if (pListHead  == NULL || NULL == pToBeDeleted)
        return;

    if (pToBeDeleted->m_pNext != NULL) 
    { 
        ListNode *pNext = pToBeDeleted->m_pNext;

        pToBeDeleted->m_pNext = pNext->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;

        delete pNext;
        pNext = NULL;
    }
    else 
    { //待删除節點為尾節點

        ListNode *pTemp = pListHead;
        while(pTemp->m_pNext != pToBeDeleted) 
            pTemp = pTemp->m_pNext;

        if (pTemp == NULL)
        {
            return ;
        }

        pTemp->m_pNext = NULL;

        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

/*
連結清單的排序--采用選擇排序算法實作 複雜度n^2
*/

ListNode* GetMinNode(ListNode *pHead)
{
    ListNode *pMin = pHead;

    ListNode*pNode = pHead;

    while(pNode != NULL)
    {
        if (pNode->m_nValue < pMin->m_nValue)
        {
            pMin = pNode;
        }
        pNode = pNode->m_pNext;
    }

    return pMin;
}
ListNode * SelectSortList(ListNode *pHead)
{
    if (pHead == NULL)
    {
        return pHead;
    }

    ListNode *pCur = pHead;
    ListNode *pMin = NULL;

    while (pCur->m_pNext != NULL)
    {
        pMin = GetMinNode(pCur->m_pNext);

        if (pMin->m_nValue < pCur->m_nValue)
        {
            int temp = pMin->m_nValue;

            pMin->m_nValue = pCur->m_nValue;
            pCur->m_nValue = temp;
        }

        pCur = pCur->m_pNext;
    }

    return pHead;
}

/*
連結清單的排序--采用歸并排序算法實作 複雜度log(n)
*/
ListNode* getMid(ListNode* node)
{
    if (node == NULL || node->m_pNext == NULL) 
    {
        return node;
    }

    ListNode* l1 = node;
    ListNode* l2 = node->m_pNext;

    while (l2 && l2->m_pNext) 
    {
        l1 = l1->m_pNext;
        l2 = l2->m_pNext->m_pNext;
    }

    return l1;
}

ListNode* MergeList(ListNode* left, ListNode* right)
{
    if (left == NULL) 
    {
        return right;
    }

    if (right == NULL) 
    {
        return left;
    }

    ListNode* temp = NULL;

    if (left->m_nValue >= right->m_nValue) 
    {
        temp = right->m_pNext;
        right->m_pNext = left;

        left = right;
        right = temp;
    }

    left->m_pNext = MergeList(left->m_pNext, right);

    return left;
}

ListNode *MergeSortList(ListNode* head)
{
    if (head == NULL || head->m_pNext == NULL) 
    {
        return head;
    }

    ListNode* mid = getMid(head);
    ListNode* right = NULL;

    if (mid != NULL) 
    {
        right = mid->m_pNext;
        mid->m_pNext = NULL;
    }

    head = MergeSortList(head);
    right = MergeSortList(right);

    head = MergeList(head, right);

    return head;
}




/*
連結清單中結點去重

第一步：連結清單排序
第二步：周遊一遍連結清單 若重複删除後者

*/

void DelRepeatNode(ListNode *pHead)
{
    if (pHead == NULL)
    {
        return;
    }

    SelectSortList(pHead);

    ListNode *pNode = pHead;

    while(pNode->m_pNext != NULL)
    {
        if (pNode->m_nValue != pNode->m_pNext->m_nValue)
        {
            pNode = pNode->m_pNext;
        }
        else
        {
            ListNode *pNext = pNode->m_pNext;
            pNode->m_pNext = pNext->m_pNext;

            delete pNext;
        }
    }
}

/*

給定連結清單中間某個節點，将待插入節點插入給定節點之前
先将待插入節點插入給定節點之後，然後交換這兩個節點資料，就相當于将帶插入節點插入給定節點之前
*/

void InsertNodeBefore(ListNode *pNode,ListNode *pToBeInsert)
{
    if (pNode == NULL || pToBeInsert == NULL)
    {
        return;
    }

    pToBeInsert->m_pNext = pNode->m_pNext;
    pNode->m_pNext = pToBeInsert;

    int temp = pToBeInsert->m_nValue;
    pToBeInsert->m_nValue = pNode->m_nValue;
    pNode->m_nValue = temp;

}


int main()
{

    ListNode *pHead = NULL;
    cout<<"尾插法建立連結清單"<<endl;
    for (int i = ;i <  ;i ++)
    {
        AddToTail(pHead,i);
    }
    cout<<"列印連結清單"<<endl;
    PrintList(pHead);

    cout<<endl;
    cout<<"擷取連結清單的節點數目"<<endl;
    cout<<GetListLength(pHead);
    cout<<endl;

    cout<<"倒序列印連結清單"<<endl;
    PrintListReverse(pHead);
    cout<<endl;

    cout<<"銷毀連結清單"<<endl;
    ReleaseList(pHead);
    cout<<endl;


    cout<<"頭插法建立連結清單"<<endl;
    for (int i = ;i <  ;i ++)
    {
        AddToHead(pHead,i);
    }
    PrintList(pHead);

    cout<<endl;
    cout<<"尋找倒數第K個節點"<<endl;
    ListNode *pKthToTail = FindKthToTail(pHead,);
    if (pKthToTail == NULL)
    {
        cout<<"NULL"<<endl;
    }
    else
    {
        cout<<pKthToTail->m_nValue<<endl;
    }

    cout<<endl;
    cout<<"反轉連結清單"<<endl;
    pHead = ReverseList(pHead);
    PrintList(pHead);


    cout<<endl;
    cout<<"查找連結清單中間節點"<<endl;
    ListNode *pNode1 = SearchMidNode(pHead);
    cout<<pNode1->m_nValue<<endl;


    cout<<endl;
    cout<<"判斷連結清單是否有環"<<endl;
    cout<<CheckCircle(pHead)<<endl;

    cout<<"銷毀連結清單"<<endl;
    ReleaseList(pHead);
    cout<<endl;

    cout<<"建立一個有環的連結清單"<<endl;
    AddToHead(pHead,);

    ListNode *p1 = pHead;

    for (int i =  ;i <  ;i ++)
    {
        AddToHead(pHead,i);
    }
    ListNode *p2 = pHead;
    p1->m_pNext =  p2;

    for (int i =  ;i <  ;i ++)
    {
        AddToHead(pHead,i);
    }
//  PrintList(pHead);//會死循環
    cout<<endl;
    cout<<"判斷連結清單是否有環"<<endl;
    cout<<CheckCircle(pHead)<<endl;

    cout<<endl;
    cout<<"判斷連結清單是否有環，并傳回環上的節點數目"<<endl;
    cout<<GetCircleNodeNum(pHead)<<endl;

    cout<<endl;
    cout<<"判斷連結清單是否有環，并傳回環上的入口節點"<<endl;
    cout<<GetEnterNodeOfCircle(pHead)->m_nValue<<endl;


//  cout<<"銷毀連結清單"<<endl;
//  ReleaseList(pHead);

    ListNode *pHead1 = NULL;


    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);

    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);
    AddToTail(pHead1,);
    cout<<endl;
    cout<<"列印連結清單"<<endl;
    PrintList(pHead1);

    cout<<endl;
    cout<<"連結清單排序"<<endl;
    pHead1 = MergeSortList(pHead1);
    PrintList(pHead1);

    cout<<endl;
    cout<<"連結清單去重"<<endl;
    DelRepeatNode(pHead1);

    cout<<endl;
    cout<<"列印連結清單"<<endl;
    PrintList(pHead1);


    {
        ListNode *pNode2 = new ListNode;
        pNode2->m_nValue = ;
        pNode2->m_pNext = NULL;

        cout<<endl;
        cout<<"給定連結清單中間某個節點，将待插入節點插入給定節點之前"<<endl;
        InsertNodeBefore(pHead1,pNode2);
        PrintList(pHead1);
    }



    return ;
}

源代碼

常見的連結清單面試題大彙總：

繼續閱讀

連結清單-Java-力扣61. 旋轉連結清單1. 題目2. 思路3. 代碼

Java複習之線程與并發一

.NET程式員面試題總結基礎知識

2014華為面試題

軟體測試工程師面試題(吐血推薦)

測試工程師面試解析～

linux下自創網絡程式設計聊天室（4）改進兩點

軟體測試：關于面試過程中的一些小總結

轉關于測試人員的職業發展

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

雲計算面試題——mysql/存儲引擎/備份

雲計算面試題——檔案/權限/分區/軟體包管理

測試理論面試題

面試題解析：你接口測試是怎麼做的？

測試面試題整理

軟體測試經典面試題（小題彙總）