本文共 10379 字，大约阅读时间需要 34 分钟。

面试官通过考察应聘者的编程语言、数据结构和算法来判断应聘者是否具备扎实的基础知识。而单链表又是数据结构中最基本的知识。

在之前的文章中，我们已经介绍过了单链表的基本功能的代码实现，下面我们就基于基本的功能，来实现一些关于单链表的经典面试题的代码编写。

链表结构定义：

typedef int DataType;typedef struct LinkNode{    DataType _data;//当前节点保存数据    struct LinkNode* _pNext;//指向链表中下一结点的指针}Node;

逆序打印单链表：

使用递归的方法来打印单链表。

//逆序打印单链表void PrintFromTail2Front(Node* pHead){    if (pHead == NULL)        return;    PrintFromTail2Front(pHead->_pNext);    printf("%d-->", pHead->_data);    printf("\n");}

删除一个无头的单链表非尾结点(不能遍历链表）：

实现起来也很简单，主要思想是删除pos位置的下一个节点，因为单链表只可以找到当前结点的下一个节点。

//删除一个无头的单链表非尾结点(不能遍历链表）void DelnotTailNode(Node* pos){    //确认pos位置及其下一位的合法性    assert(pos);    assert(pos->_pNext);    Node* pD = pos->_pNext;    pos->_data = pD->_data;    pos->_pNext = pD->_pNext;    free(pD);    pD = NULL;}

不允许遍历链表，在pos之后插入

//不允许遍历链表，在pos之后插入void LinkListInsertAfter( Node* pos, DataType data){    assert(pos);    if (pos == NULL)    {        return;    }    Node* NewNode = LinkListCreatNode(data);    NewNode->_pNext = pos->_pNext;    pos->_pNext = NewNode;}

不允许遍历链表，在pos之前插入

这个问题我是在基于在pos之后插入的问题解决，只要在pos之后插入，然后交换pos和pos->next的值，就相当于在不遍历链表的前提下完成了在pos之前插入。

//不允许遍历链表，在pos之前插入void LinkListInsertBefore(Node** pHead, Node* pos, DataType data){    assert(pHead);    assert(*pHead);    LinkListInsertAfter(pos, data);    DataType tmp = pos->_data;    pos->_data = pos->_pNext->_data;    pos->_pNext->_data = tmp;}

单链表实现约瑟夫环

//单链表实现约瑟夫环(JosephCircle)Node* JosephCircle(Node* pHead, int  M){    assert(pHead);    Node* pCur = pHead;    Node* pDel = NULL;    //在删除一个结点之后，要让其前一个节点指向其后一个结点，    //若其前一个节点指向其后一个结点使同一个结点    //则说明环中只剩最后一个结点结束    while (pCur->_pNext!=pCur)    {        //1.报数        int count = M;        while (--count)            pCur = pCur->_pNext;        //2.删除结点        //删除pCur的下一个结点，将pCur与pCur->_pNext的data互换        pDel = pCur->_pNext;        pCur->_data = pDel->_data;        pCur->_pNext = pDel->_pNext;        free(pDel);    }    return pCur;}

查找单链表中间结点，要求只能遍历一次链表

//查找单链表的中间节点，要求只能遍历一次链表Node* LinkFindMiddeNode(Node* pHead){    assert(pHead);    Node* pFast = pHead;    Node* pSlow = pHead;    while (pFast && pFast->_pNext!=NULL)    {        pFast = pFast->_pNext->_pNext;        pSlow = pSlow->_pNext;    }    printf("中间结点是：%d", pSlow->_data);    return pSlow;}

查找单链表的倒数第K个结点，要求只能遍历一次链表

//查找单链表的倒数第K个结点，要求只能遍历一次链表Node* LinkFindLastKNode(Node* pHead,int K){    assert(pHead);    Node* pFast = pHead;    Node* pSlow = pHead;    for (int i = 0; i < K; i++)    {        if (pFast == NULL)            return 0;        //先让快指针走K-1步        pFast = pFast->_pNext;    }    while (pFast&& pFast->_pNext != NULL)    {        pFast = pFast->_pNext;        pSlow = pSlow->_pNext;    }    printf("倒数第%d个结点是%d\n", K, pSlow->_data);    return pSlow;}

删除单链表倒数第K个结点

//删除链表的倒数第K个结点void LinkDelLastKNode(Node* pHead, int K){    assert(pHead);    size_t len = LinkListSize(&pHead);    if (K > len)        return;    //当删除结点为倒数第size个时，相当头删    if (K == len)    {        LinkListPopFront(pHead);//头删包含头指针的指向改变        return;    }    //找到倒数第K个结点    Node* pFast = pHead;    for (int i = 0; i < len-K-1; i++)    {        pFast = pFast->_pNext;    }    //删除该结点    Node* pDel = pFast->_pNext;    pFast->_pNext = pDel->_pNext;    LinkListIDestroyNode(pDel);}

单链表的逆置（1）—改变指针指向

//链表的逆置----改变//方式一：改变指针指向void* LinkListReverse1(Node** pHead){    assert(pHead);    Node* pPre = NULL;    Node* pCur = *pHead;    Node* pNext = NULL;    while (pCur)    {        pNext = pCur->_pNext;        pCur->_pNext = pPre;        pPre = pCur;        pCur = pNext;    }    *pHead = pPre;    return;}

单链表的逆置（2）—采取头插的思想

//方式二：头插方式Node* LinkListReverse2(Node* pHead){    Node* NewpHead = NULL;    Node* pCur = pHead;    Node* pNext = NULL;    while (pCur)    {        pNext = pCur->_pNext;        pCur->_pNext = NewpHead;        NewpHead = pCur;        pCur = pNext;    }    return NewpHead;}

合并两个有序链表，合并之后依然有序

//合并两个有序链表，合并之后依然有序Node* LinkListMerge(Node* pHead1, Node* pHead2){    assert(pHead1);    assert(pHead2);    Node* pCur1 = pHead1;    Node* pCur2 = pHead2;    Node* new_head = NULL;    Node* new_tail = NULL;    //尾插第一个结点    if (pCur1->_data >= pCur2->_data)    {        new_head = new_tail= pCur2;        pCur2 = pCur2->_pNext;    }    else    {        new_head = new_tail = pCur1;        pCur1 = pCur1->_pNext;    }    //尾插后续结点    while (pCur1  && pCur2 )    {        if (pCur1->_data >= pCur2->_data)        {            new_tail->_pNext = pCur2;            pCur2 = pCur2->_pNext;        }        else        {            new_tail->_pNext = pCur1;            pCur1 = pCur1->_pNext;        }        new_tail = new_tail->_pNext;    }    //当pHead1还有剩余结点时，将剩余结点尾插至NewpHead    if (pCur1)        new_tail->_pNext = pCur1;    //当pHead2还有剩余结点时，将剩余结点尾插至NewpHead    else  //(pCur2)        new_tail->_pNext = pCur2;    return new_head;}

单链表的冒泡排序

冒泡排序的基本思想是将相邻两元素间两两比较，一趟排序过后，最大的元素就到达了最后。单链表的冒泡排序也是如此，万变不离其宗，我们直接上代码：

//单链表的冒泡排序//冒泡排序的基本思想是将相邻两元素间两两比较，一趟排序过后，//最大的元素就到达了最后。单链表的冒泡排序也是如此，万变不离其宗，我们直接上代码：//升序void LinkBubbleSort(Node* pHead){    //空链表或者链表只有一个结点，都不用排序    if (pHead == NULL || pHead->_pNext == NULL)    {        return;    }    Node* pTail = NULL;    while (pHead != pTail)    {        Node* pPre = pHead;        Node* pCur = pPre->_pNext;        while (pCur != pTail)        {            if (pPre->_data > pCur->_data)            {                DataType temp = pPre->_data;                pPre->_data = pCur->_data;                pCur->_data = temp;            }            pPre = pCur;            pCur = pCur->_pNext;        }        pTail = pPre;    }}

判断链表是否带环

//判断链表是否带环void If_HasCycle(Node* pHead){    if (pHead == NULL || pHead->_pNext == NULL)    {        return;    }    Node* pFast = pHead;    Node* pSlow = pHead;    while (pFast != NULL)    {        pFast = pFast->_pNext->_pNext;        pSlow = pSlow->_pNext;        if (pFast == pSlow)            return pSlow;    }               return NULL;}

若链表带环，求环长度

判断是否带环函数返回值即为相遇点（两指针在环内的交点），然后把环遍历一遍就行了

//若带环，求环长度size_t LinkCycle_Len(Node* pHead){    assert(pHead);    //判断是否带环函数返回值即为相遇点    Node* Meet_Node = If_HasCycle(pHead);    if (Meet_Node == NULL)    {        return 0;    }    size_t len = 1;    Node* pCur = Meet_Node->_pNext;    for (pCur; pCur != Meet_Node; pCur = pCur->_pNext)    {        len++;    }    return len;}

若链表带环，求环的入口点

这个问题需要一定的数学推理，先把结论列出来：

相遇点node到入口点的距离=头指针到连接点的距离，因此，分别从相遇点、头指针开始走，相遇的那个点就是连接 假设链表总长为L，头节点到入口点的距离为a,入口点到快慢指针交点距离为x,环的长度为R，现在假设慢指针走了S步与快指针相遇， s = a + x; 那么快指针走了2S步， 2s = a + nr + x; 就可以得到：a + x = nr; ->a = nr - x; 可以看出来，头节点到入口点的距离等于交点到入口点的距离 那我们让两个指针，一个从相遇点走，一个从头节点走，最后一定在入口点相遇。

先判断链表是否带环，若带环，则返回的即是相遇点，定义两个指针一个指向pHead，一个指向相遇点，两指针均一次走一步，则两指针相遇处即为环的入口点

//若带环，求环的入口点Node* GetCycleEntry(Node* pHead){    if (pHead == NULL ||pHead->_pNext==NULL)    {        return NULL;    }    Node* Meet_Node = If_HasCycle(pHead);    if (Meet_Node == NULL)    {        return NULL;    }    Node* pCur = pHead;    Node* pM = Meet_Node;    while (pCur != pM)    {        pCur = pCur->_pNext;        pM = pM->_pNext;    }    return pCur;}

求两个已排序单链表中相同的数据

//求两个已排序单链表中相同的数据Node* UnionSet(Node* pHead1, Node* pHead2){    if (pHead1 == NULL || pHead2 == NULL)    {        return;    }    Node* pCur1 = pHead1;    Node* pCur2 = pHead2;    Node* newHead = NULL;    Node* newTail = NULL;    while (pCur1 && pCur2)    {        if (pCur1->_data < pCur2->_data)            pCur1 = pCur1->_pNext;        else if (pCur1->_data>pCur2->_data)            pCur2 = pCur2->_pNext;        else        {            Node* new_Node = LinkListCreatNode(pCur1->_data);            if (newHead == NULL)                newHead = newTail = new_Node;            else            {                newTail->_pNext = new_Node;                newTail = newTail->_pNext;            }               pCur1 = pCur1->_pNext;            pCur2 = pCur2->_pNext;        }    }    return newHead;}

复杂链表的复制

一个链表的每个节点，有一个next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表

准备工作： 1.定义复杂链表结构类型

//定义复杂链表的结构类型typedef struct ComplexNode{    DataType _data;//当前结点数据    struct ComplexNode* _pNext;//指向下一结点的指针    struct ComplexNode* _random;//指向随机结点或者NULL的指针}CNode;

2.编写三个基本功能的函数来实现初始化、打印、创造节点和插入结点

//打印void ComplexPrint(CNode* pHead){    assert(pHead);    CNode* pCur = pHead;    for (pCur; pCur != NULL; pCur = pCur->_pNext)    {        printf("%d--->", pCur->_data);    }    printf("NULL\n");}//初始化void ComplexInit(CNode** pHead){    assert(pHead);    *pHead = NULL;}//创建新结点CNode* ComplexCreatNode(DataType data){    CNode* newNode = (CNode*)malloc(sizeof(CNode));    newNode->_data = data;    newNode->_pNext = NULL;    newNode->_random = NULL;    return newNode;}//尾插void ComplexLinkPushBack(CNode** pHead, DataType data){    CNode* NewNode = ComplexCreatNode(data);    assert(pHead);    //如果链表为空，则直接让头指针指向新申请的节点即可    if (*pHead == NULL)    {        *pHead = NewNode;        return;    }    //否则从头开始遍历链表，直到当前节点的指针域指向NULL，然后让当前节    //点的指针域指向新申请的节点即可    CNode* pTail = *pHead;    while (pTail->_pNext)    {        pTail = pTail->_pNext;    }    pTail->_pNext = NewNode;}

3.复杂链表的复制

//在原链表中求各random的相对偏移量size_t Diff(CNode* src,CNode* dst){    if (src == NULL || dst == NULL)    {        return (size_t)-1;    }    size_t count = 0;    while(src != NULL)    {        if (src == dst)            break;        ++count;        src = src->_pNext;    }    return count;}//求偏移位数CNode* Step(CNode* pos,size_t offset){    size_t i = 0;    for (; i < offset; i++)    {        if (pos == 0)            return NULL;        pos = pos->_pNext;    }    return pos;}

最后实现复制目的的函数：

//复杂链表的复制CNode* ComplexCopy(CNode* pHead){    assert(pHead);    //先将单链表进行简单复制    CNode* pCur = pHead;    CNode* newHead = NULL;    CNode* newTail = NULL;    for (pCur; pCur != NULL; pCur = pCur->_pNext)    {        CNode* newNode = ComplexCreatNode(pCur->_data);        if (newHead == NULL)            newHead = newTail = newNode;        else        {            newTail->_pNext = newNode;            newTail = newTail->_pNext;        }    }    //再依次求每个random指针相对头节点的偏移量    //根据偏移量，修改每个新链表节点的random指针    CNode* new_pCur = newHead;    for (pCur = pHead; pCur != NULL&&new_pCur != NULL;        pCur = pCur->_pNext, new_pCur = new_pCur->_pNext)    {        //原始偏移量为空，不变        if (pCur->_random == NULL)        {            new_pCur->_random = NULL;            continue;        }        //根据偏移量，修改每个新链表节点的random指针          size_t offset = Diff(pHead, pCur->_random);        new_pCur->_random = Step(newHead, offset);    }    return newHead;}