常见的链表面试题大汇总：

源代码下载链接
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/存储引擎/备份

云计算面试题——文件/权限/分区/软件包管理

测试理论面试题

面试题解析：你接口测试是怎么做的？

测试面试题整理

软件测试经典面试题（小题汇总）
