链表面试题集合

淡淡的烟草味﹌ 2022-05-09 00:18 204阅读 0赞

链表面试题：

1. 比较顺序表和链表的优缺点,说说它们分别在什么场景下使用?

*  顺序表一般用于查找，可随机访问；
 *  链表一般用于增删改，不可随机访问；
 *  如果数据元素不多，两种方式没有太大的差别
 *  如果数据元素不定，建议使用链表
 *  顺序表的CPU高速缓存效率高，而单链表CPU高速缓存效率低。

链表的基本操作如下：

#include "List.h"
    
    void InitLinkList(pList* pplist)
    {
        (*pplist) = NULL;
    }
    
    pNode BuyNode(DataType d)
    {
        pNode newNode = (pNode)malloc(sizeof(Node));
        if (newNode == NULL)
        {
            perror("malldc error");
            exit(EXIT_FAILURE);
        }
        newNode->data = d;
        newNode->next = NULL;
        return newNode;
    }
    
    void DestroyLinkList(pList* pplist)
    {
        assert(pplist);
        pNode cur = NULL;
        cur = *pplist;
        while (cur)
        {
            pNode del = cur;
            cur = cur->next;
            free(del);
            del = NULL;
        }
        *pplist = NULL;
    }
    
    void PushBack(pList* pplist, DataType d)
    {
        assert(pplist);
        pNode newNode = BuyNode(d);
        if ((*pplist) == NULL)
        {
            *pplist = newNode;
        }
        else
        {
            pNode cur = NULL;
            cur = *pplist;
            while (cur->next)
            {
                cur = cur->next;
            }
            cur->next = newNode;
        }
    }
    
    void PopBack(pList* pplist)
    {
        assert(pplist);
        if ((*pplist) == NULL)
        {
            printf("链表为空！\n");
            return;
        }
        else
        {
            pNode cur = NULL;
            pNode del = NULL;
            cur = *pplist;
            del = cur->next;
            while (cur->next->next)
            {
                cur = cur->next;
                del = cur->next;
            }
            cur->next = del->next;
            free(del);
            del = NULL;
        }
    }
    
    void PushFront(pList* pplist, DataType d)
    {
        pNode newNode = BuyNode(d);
        assert(pplist);
        if ((*pplist) == NULL)
        *pplist = newNode;
        else
        {
            pNode cur = *pplist;
            newNode->next = cur;
            *pplist = newNode;
        }
    }
    
    void PopFront(pList* pplist)
    {
        assert(pplist);
        if ((*pplist) == NULL)
        {
            printf("链表为空！\n");
            return;
        }
        else
        {
            pNode del = NULL;
            del = *pplist;
            *pplist = (*pplist)->next;
            free(del);
            del = NULL;
        }
    }
    
    pNode Find(pList plist, DataType d)
    {
        if (plist == NULL)
        {
            printf("链表为空！\n");
            return NULL;
        }
        else
        {
            pNode cur = plist;
            while (cur)
            {
                if (cur->data == d)
                {
                    return cur;
                }
                cur = cur->next;
            }
            return NULL;
        }
    }
    
    void Insert(pList* pplist, pNode pos, DataType d)//在指定位置之前插入一个值
    {
        assert(pplist);
        assert(pos);
        assert(*pplist);
        pNode newNode = BuyNode(d);
        if (pos == (*pplist))
        {
            newNode->next = *pplist;
            *pplist = newNode;
        }
        else
        {
            pNode cur = *pplist;
            while (cur&&cur->next != pos)
            {
                cur = cur->next;
            }
            if (cur)
            {
                newNode->next = pos;
                cur->next = newNode;
            }
        }
    }
    
    void Erase(pList* pplist, pNode pos)//指定位置删除
    {
        assert(pplist);
        assert(pos);
        if ((*pplist) == NULL)
        {
            return;
        }
        if ((*pplist) == pos)
        {
            *pplist = pos->next;
            free(pos);
            pos = NULL;
        }
        else
        {
            pNode cur = *pplist;
            while (cur&&cur->next != pos)
            {
                cur = cur->next;
            }
            if (cur)
            {
                cur->next = pos->next;
                free(pos);
                pos = NULL;
            }
        }
    }
    
    void Remove(pList* pplist, DataType d)
    {
        assert(pplist);
        pNode cur = *pplist;
        if ((*pplist) == NULL)
        {
            return;
        }
        if ((*pplist)->data == d)
        {
            *pplist = cur->next;
            free(cur);
            cur = NULL;
        }
        else
        {
            pNode del = cur;
            while (cur&&del->data != d)
            {
                cur = cur->next;
                del = cur->next;
            }
            if (cur)
            {
                cur->next = del->next;
                free(del);
                del = NULL;
            }
        }
    }
    
    //void ReMoveP(pList* pplist, DataType d) 
    //{
    //     pNode pCur = NULL;
    //     pNode pre = NULL;
    //     assert(pplist);
    //     if (NULL == (*pplist))
    //     {
    //         return;
    //     }
    //     pCur = (*pplist);
    //
    //     while (pCur)
    //     {
    //         pNode pDel = NULL;
    //         if (pCur->data == d)
    //         {
    //             if ((*pplist)->data == d)
    //             {
    //                 pCur = *pplist;
    //                 *pplist = (pCur)->next;
    //                 free(pCur);
    //                 pCur = *pplist;
    //             }
    //             else
    //             {
    //                 pre->next = pCur->next;
    //                 free(pCur);
    //                 pCur=pre;
    //
    //             }
    //         }
    //         else
    //         {
    //             pre = pCur;
    //             pCur = pCur->next;
    //         }
    //     }
    //}
    
    void RemoveAll(pList* pplist, DataType d)
    {
        assert(pplist);
        pNode cur = *pplist;
        if ((*pplist) == NULL)
        {
            return;
        }
        pNode pre = *pplist;
        while (cur)
        {
            if ((*pplist)->data == d)
            {
                cur = *pplist;
                *pplist = (cur)->next;
                free(cur);
                cur = *pplist;
            }
            else if (cur->data == d)
            {
                pre->next = cur->next;    
                free(cur);
                cur = pre->next;
            }
            pre = cur;
            cur = cur->next;
        }
    }
    
    void PrintLinkList(pList plist)
    {
        pNode cur = plist;
        while (cur)
        {
            printf("%d->", cur->data);
            cur = cur->next;
        }
        printf("NULL\n");
    }
    
    int GetListLength(pList plist)
    {
        int count = 0;
        pNode cur = plist;
        while (cur)
        {
            count++;
            cur = cur->next;
        }
        return count;
    }

2. 从尾到头打印单链表

*  递归调用

void PrintTailToHead1(pList plist)//递归逆序打印单项链表
    {
        if (plist == NULL)
        return;
        PrintTailToHead1(plist->next);
        printf("%d ", plist->data);
    }

*  非递归，时间复杂度O(n^2)。

void PrintTailToHead2(pList plist)//非递归逆序打印单项链表
    {
        pNode tail = NULL;
        pNode cur = plist;
        if (plist == NULL)
            return;
        while (plist != tail)
        {
            while (cur->next != tail)
            {
                cur = cur->next;
            }
            printf("%d ", cur->data);
            tail = cur;
            cur = plist;
        }
    }

3. 删除一个无头单链表的非尾节点

![70][]

void EraseNotTailNode(pNode pos)
    {
        assert(pos);
        assert(pos->next);
        pNode del = NULL;
        del = pos->next;
        pos->data = pos->next->data;
        pos->next = del->next;
        free(del);
        del = NULL;
    }

4. 在无头单链表的一个节点前插入一个节点  
![70 1][]

void InsertNode(pList* pplist, pNode pos, DataType d)//在无头单链表的一个节点之前插入一个节点
    {
        assert(pplist);
        assert(pos);
        assert(*pplist);
        pNode newNode = BuyNode(pos->data);
        newNode->next = pos->next;
        pos->next = newNode;
        pos->data = d;
    }

5. 单链表实现约瑟夫环

方法一：

![70 2][]

int pLinkNodeJosephCycle(pList * pplist, int num)
    {
        pList tmp = NULL;
        pList p = NULL;
        p = (*pplist);
        tmp = (*pplist);
        while (tmp->next)
        {
            tmp = tmp->next;
        }
        tmp->next = (*pplist);
        while ((*pplist) != (*pplist)->next)
        {
            for (int i = 1; i < num - 1; i++)
            {
                (*pplist) = (*pplist)->next;
            }
            p = (*pplist)->next;
            (*pplist)->next = p->next;
            free(p);
            p = NULL;
            (*pplist) = (*pplist)->next;
        }
        return (*pplist)->data;
    }

方法二：

![70 3][]

void JosephCycle(pList * pplist, int num)
    {
        pList p = NULL;
        p = (*pplist);
        while (p!=p->next)
        {
            pNode del = NULL;
            int count = num;
            while(--count)
            {
                p=p->next;
            }
            printf("删除:%d\n",p->data);
            del=p->next;
            p->data = del->data;
            p->next = del->next;
            free(del);
            del = NULL;
        }
    }

6. 逆置/反转单链表

![70 4][]

void ReverseList(pList* pplist)
    {
        pList q = (*pplist);
        pList p = q->next;
        while (p)  //当p指向NULL时，表明倒置完成，退出循环
        {
            q->next = p->next;
            p->next = (*pplist);
            (*pplist) = p;
            p = q->next;
        }
    }

7. 单链表排序（冒泡排序）

void BubbleSort(pList * pplist)
    {
        assert(pplist);
        assert(*pplist);
        pList q = NULL;
        pList p = NULL;
        for (int i = 0; i < GetListLength(*pplist); i++)
        {
            pList q = (*pplist);
            pList p = q->next;
            for (int j = 0; j < GetListLength(*pplist) - i - 1; j++)
            {
                while (p)
                {
                    if (q->data < p->data)
                    {
                        DataType tmp = q->data;
                        q->data = p->data;
                        p->data = tmp;
                    }
                    p = p->next;
                    q = q->next;
                }
            }
        }
    }

8. 合并两个有序链表,合并后依然有序  
//递归

pNode Merge_R(pList plist1, pList plist2)//递归合并两个有序链表
    {
        pNode  cur1 = plist1;
        pNode  cur2 = plist2;
        pNode  newlist = NULL;
        if (cur1 == cur2)
            return NULL;
        if (cur1 == NULL)
            return cur2;
        if (cur2 == NULL)
            return cur1;
        if (cur1->data < cur2->data)
        {
            newlist = cur1;
            newlist->next = Merge_R(cur1->next,cur2);
        }
        else
        {
            newlist = cur2;
            newlist->next = Merge_R(cur1,cur2->next);
        }
        return newlist;
    }

pNode Merge(pList plist1, pList plist2)//非递归合并两个有序链表
    {
        pNode  cur1 = plist1;
        pNode  cur2 = plist2;
        pNode  head = NULL;
        pNode  tail = NULL;
        if (cur1 == NULL&&cur2 == NULL)//两条都为空不合并
            return NULL;
        if (cur1 == cur2)
            return cur1;
        if (cur1 == NULL)
            return cur2;
        if (cur2 == NULL)
            return cur1;
        if (cur1->data > cur2->data)
        {
            head = cur1;
            cur1 = cur1->next;
        }
        else
        {
            head = cur2;
            cur2 = cur2->next;
        }
        head->next = NULL;
        tail = head;
        while (cur1 != NULL&&cur2 != NULL)
        {
            if (cur1->data > cur2->data)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail->next->next = NULL;
            tail = tail->next;
        }
        if (cur1 == NULL)
        {
            tail->next = cur2;
        }
        else
            tail->next = cur1;
        return head;
    }

9. 查找单链表的中间节点，要求只能遍历一次链表

![70 5][]

pNode FindMidNode(pList plist)//找中间节点
    {
        pList fast = NULL;
        pList slow = NULL;
        if (NULL == plist)
        {
            return NULL;
        }
        else
        {
            //快慢指针
            slow = plist;
            fast = plist;
            while ((NULL != fast) && (NULL != fast->next))
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
    }

10. 查找单链表的倒数第k个节点，要求只能遍历一次链表

pNode FindLastKNode(pList plist, int k)
    {
        if ((NULL == plist) || (k <= 0))
        {
            return NULL;
        }
        else
        {
            pNode fast = plist;
            pNode slow = plist;
            //利用快慢指针，让快指针先走K-1步，然后两指针同时走，直到快指针指向的下一个结点为空为止
            while (--k)
            {
                fast = fast->next;
                if (NULL == fast)
                {
                    return NULL;
                }
            }
            while (NULL != fast->next)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }

11. 判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度。

pNode CheckCycle(pList pList)
    {
        if ((NULL == pList) || (NULL == pList->next))
        {
            return NULL;
        }
        else
        {
            pNode pFast = pList->next->next;
            pNode pSlow = pList->next;
            while (pFast != pSlow)
            {
                if (NULL == pFast)
                {
                    return NULL;
                }
                else
                {
                    pFast = pFast->next;
                    pSlow = pSlow->next;
                    if (NULL == pFast)
                    {
                        return NULL;
                    }
                    else
                    {
                        pFast = pFast->next;
                    }
                }
            }
            return pFast;
        }
    }

int GetCircleLength(pNode meet)
    {
        if (NULL == meet)
        {
            return 0;
        }
        else
        {
            int count = 1;
            pNode pnode = meet;
            while (meet != pnode->next)
            {
                pnode = pnode->next;
                count++;
            }
            return count;
        }
    }

pNode GetCycleEntryNode(pList plist, pNode meetNode)
    {
        pNode pnode = plist;
        if ((NULL == plist) || (NULL == meetNode))
        {
            return NULL;
        }
        while (pnode != meetNode)
        {
            pnode = pnode->next;
            meetNode = meetNode->next;
        }
        return pnode;
    }

12. 判断两个链表是否相交，若相交，求交点。（假设链表不带环）

int CheckCross(pList p1, pList p2)
    {
        if((p1==NULL)||(p2==NULL))
            return 0;
        pNode end1=p1;
        pNode end2=p2;
        while(end1->next!=NULL)
            end1=end1->next;
        while(end2->next!=NULL)
            end2=end2->next;
        if(end1==end2)
            return 1;
        else return 0;
    }

13. 判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】

![70 6][]

[70]: /images/20220509/5ee6046018f54292bbb3ab746267273c.png
[70 1]: /images/20220509/9f63eea3804e4694b0915e7e2bc100d7.png
[70 2]: /images/20220509/9fbe585638504aeeb19bbc9769a9eb07.png
[70 3]: /images/20220509/afced93be7aa401ebdaecc7e3ffb0870.png
[70 4]: /images/20220509/d0207b5e61a243b1a423a05ab92d998f.png
[70 5]: /images/20220509/18be86e65f684cb9a8417975977ac1f2.png
[70 6]: /images/20220509/eba547868a494d0dad91bf13a95ead5c.png