2022-04-28 09:53 已编辑

关注

面试官：给你十分钟，写出可以增删查改任意位置插入删除的链表！

我有一个师兄，前几年去面试，笔试过了，到了面试环节，面试官提出了一个让他觉得面试官在为难他的一个问题：给你十分钟，写出可以增删查改任意位置插入删除的链表！
当时他一下子感觉这是不可能的，因为众所周知——链表的接口有初始化、打印、头插、头删、尾插、尾删、中间插入、中间删除、查找等这么多接口函数，看这些名字就知道把这些写完需要不少时间。
师兄说，他最快也要25分钟（他当时没有想到用双向循环带头链表），结果可想而知（挂了(；´д｀)ゞ），后来回去他与老师探讨这一题，老师笑而不语，写下了：双向循环带头链表，师兄才恍然大悟！！！！
下面我来分享这道题的解法：
首先先讲解一下双向循环带头链表的各种接口，会在最后写下这道题的解法，如果不想看这些接口，可以直接划到最后看这道题的解法。
——————————————————————————————

1.链表的分类：

单向、双向
带头、不带头
循环、非循环

今天我们就来讲一讲链表中看似结构复杂的==双向循环带头链表==：
图片说明

2.双向链表的初始化：

方法一：传双指针

void ListNodeInit(ListNode** pphead)
{
    *pphead = ListNodeBuy(0);
    //ListNodeBuy（0）是建立一个存储0的地址的函数，后面会写上这个函数
    (* pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}

方法二：==返回值==法

ListNode* ListNodeInit()
{
    ListNode* phead = ListNodeBuy(0);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

再加上主函数上写：

ListNode* phead=ListNodeInit();

即可完成双向链表的初始化。

PS：双向循环带头链表为空时，即是只有头指针时，head->next和head->prev均指向自己（head）

3.双向链表的打印

（1）运行代码：

void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

这里要记得双向循环带头链表打印时的终止条件是：当cur遍历回到了phead！

（2）运行结果：

图片说明

4.双向链表的尾插：

（1）运行代码：

由于插入时要创建一个变量newnode，需向内存申请空间存储变量，且变量的值为插入的值，又因为每次插入都需要这一步，故将这一步写成一个函数，便于使用该函数为：

ListNode* ListNodeBuy(LTDataType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->next = NULL;
    newnode->prev = NULL;
    newnode->data=x;
    return newnode;
}

尾插函数：

void ListNodePushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* tail = phead->prev;
    ListNode* newnode = ListNodeBuy(x);
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

（2）运行结果：

图片说明

5.双向链表的尾删

（1）运行代码：

void ListNodePopBack(ListNode* phead)
{
    assert(phead);
    //这是调用断言函数，该表达式的意思为判断phead是否为NULL
    assert(phead->next != phead);
    //这是判断该链表是否为空链表，若为空链表，则会报错
    ListNode* tail = phead->prev;
    ListNode* tail_prev = tail->prev;
    tail_prev->next = phead;
    phead->prev = tail_prev;
    free(tail);
    tail = NULL;
}

assert(phead);//这是调用==断言函数==，该表达式的意思为判断phead是否为NULL
assert(phead->next != phead);//这是判断该链表是否为==空链表==，若为空链表，则会报错

（2）运行结果：

图片说明

5.双向链表的头插：

（1）运行代码：

void ListNodePushFront(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* first = phead->next;
    ListNode* newnode = ListNodeBuy(x);
    phead->next = newnode;
    newnode->next = first;
    newnode->prev = phead;
    first->prev = newnode;
}

注：头插是是将==newnode==插在==phead==和==first==（头结点后的第一个结点）
图片说明

（2）运行结果：

图片说明

7.双向链表的头删：

（1）运行代码：

void ListNodePopFront(ListNode* phead)
{
    assert(phead);
    //这是调用断言函数，该表达式的意思为判断phead是否为NULL
    assert(phead->next != phead);
    //这是判断该链表是否为空链表，若为空链表，则会报错
    ListNode* first = phead->next;
    ListNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;
}

图片说明

（2）运行结果：

图片说明

8.双向链表的查找

（1）运行代码：

ListNode* ListNodeFind(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

查找后返回的是结点的指针，可以用==pos->data=某个数==进而修改这个点的值！！！

（2）运行结果：

图片说明

9.双向链表的中间插入：

（1）运行代码：

插入在指定位置的前面

void ListNodeInsert(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* pos_prev = pos->prev;
    ListNode* newnode = ListNodeBuy(x);
    newnode->next = pos;
    pos->prev = newnode;
    pos_prev->next = newnode;
    newnode->prev = pos_prev;
}

（2）运行结果：

图片说明

10.双向链表的中间删除：

（1）运行代码：

void ListNodeErase(ListNode* pos)
{
    assert(pos);
    ListNode* pos_prev = pos->prev;
    ListNode* next = pos->next;
    free(pos);
    pos = NULL;
    pos_prev->next = next;
    next->prev = pos_prev;
}

（2）运行结果：

图片说明

11.双向链表的销毁：

每一次用完链表后销毁是很有必要的，如果不销毁，将会导致==内存的泄露==，短时间内可能没用什么，且很难被发现，但时间长了，必将导致==程序的崩溃==，最终将导致时间和金钱的浪费！！！
这里介绍两种销毁：
方法一：销毁全部，不保留头结点：

void ListNodeDestroy(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = NULL;
        cur = next;
    }
    free(phead);
    phead=NULL;
}

方法二：保留头结点：

void ListNodeDestroy(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = NULL;
        cur = next;
    }
}

具体选择哪一种，需要看==实际需要==！！！

12.完整代码：

（1）List.h文件：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* prev;
    LTDataType  data;
    struct ListNode* next;
}ListNode;
ListNode* ListNodeBuy(LTDataType x);
void ListNodeInit(ListNode** pphead);
void ListPrint(ListNode* phead);
void ListNodePushBack(ListNode* phead, LTDataType x);
void ListNodePopBack(ListNode* phead);
void ListNodePushFront(ListNode* phead, LTDataType x);
void ListNodePopFront(ListNode* phead);
ListNode* ListNodeFind(ListNode* phead, LTDataType x);
void ListNodeInsert(ListNode* pos, LTDataType x);
void ListNodeErase(ListNode* pos);
void ListNodeDestroy(ListNode* phead);

（2）List.c文件：

#include"List.h"
#define _CRT_SECURE_NO_WARNINGS 1
ListNode* ListNodeBuy(LTDataType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->next = NULL;
    newnode->prev = NULL;
    newnode->data=x;
    return newnode;
}
void ListNodeInit(ListNode** pphead)
{
    *pphead = ListNodeBuy(0);
    (* pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}
ListNode* ListNodeInit()
{
    ListNode* phead = ListNodeBuy(0);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
void ListNodePushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* tail = phead->prev;
    ListNode* newnode = ListNodeBuy(x);
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}
void ListNodePopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    ListNode* tail = phead->prev;
    ListNode* tail_prev = tail->prev;
    tail_prev->next = phead;
    phead->prev = tail_prev;
    free(tail);
    tail = NULL;
}
void ListNodePushFront(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* first = phead->next;
    ListNode* newnode = ListNodeBuy(x);
    phead->next = newnode;
    newnode->next = first;
    newnode->prev = phead;
    first->prev = newnode;
}
void ListNodePopFront(ListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    ListNode* first = phead->next;
    ListNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;
}
ListNode* ListNodeFind(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
void ListNodeInsert(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* pos_prev = pos->prev;
    ListNode* newnode = ListNodeBuy(x);
    newnode->next = pos;
    pos->prev = newnode;
    pos_prev->next = newnode;
    newnode->prev = pos_prev;
}
void ListNodeErase(ListNode* pos)
{
    assert(pos);
    ListNode* pos_prev = pos->prev;
    ListNode* next = pos->next;
    free(pos);
    pos = NULL;
    pos_prev->next = next;
    next->prev = pos_prev;
}
void ListNodeDestroy(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = NULL;
        cur = next;
    }
}
## （3）test.c文件：

```c
#include"List.h"
#define _CRT_SECURE_NO_WARNINGS 1
int main(void)
{
    ListNode* phead = NULL;
    ListNodeInit(&phead);
    /*ListNodePushBack(phead, 1);
    ListNodePushBack(phead, 2);
    ListNodePushBack(phead, 3);
    ListNodePushBack(phead, 4);
    ListNodePushBack(phead, 5);
    ListNodePushBack(phead, 6);
    ListPrint(phead);
    ListNodePopBack(phead, 1);
    ListNodePopBack(phead, 2);
    ListNodePopBack(phead, 3);
    ListNodePopBack(phead, 4);
    ListNodePopBack(phead, 5);
    ListPrint(phead);*/
    ListNodePushFront(phead, 1);
    ListNodePushFront(phead, 2);
    ListNodePushFront(phead, 3);
    ListNodePushFront(phead, 4);
    ListNodePushFront(phead, 5);
    ListNodePushFront(phead, 6);
    ListPrint(phead);
    /*ListNodePopFront(phead, 1);
    ListNodePopFront(phead, 2);
    ListNodePopFront(phead, 3);
    ListNodePopFront(phead, 4);
    ListNodePopFront(phead, 5);
    ListPrint(phead);*/
    ListNode* pos = ListNodeFind(phead,3);
    pos->data = 300;
    ListPrint(phead);
    ListNodeInsert(pos, 1);
    ListPrint(phead);
    ListNodeErase(pos);
    ListPrint(phead);
    ListNodeDestroy(phead);
    return 0;
}

13.这道面试题的解法：

这道题的解法：
首先先写一个结构体，然后
void ListNodeInit(ListNode* pphead);初始化（写出函数）
void ListPrint(ListNode phead);只写函数名，这个即可
void ListNodePushBack(ListNode* phead, LTDataType x);只写函数名，这个即可
void ListNodePopBack(ListNode* phead);只写函数名，这个即可
void ListNodePushFront(ListNode* phead, LTDataType x);只写函数名，这个即可
void ListNodePopFront(ListNode* phead);只写函数名，这个即可
以上这几个函数只写函数名即可，面试官会理解这些的函数的作用
ListNode* ListNodeFind(ListNode* phead, LTDataType x);写出函数
void ListNodeInsert(ListNode* pos, LTDataType x);写出函数
void ListNodeErase(ListNode* pos);写出函数
这三个函数是大头，要写出函数操作。
如果你最后还是不放心，可以把这些写成这样：
请在这里输入引用内容
void ListNodePushBack(ListNode* phead, LTDataType x)
{ ListNodeInsert(phead,x);}
void ListNodePopBack(ListNode* phead)
{ ListNodeErase(phead->prev); }
void ListNodePushFront(ListNode* phead, LTDataType x)
{ ListNodeInsert(phead->next,x);}
void ListNodePopFront(ListNode* phead)
{ ListNodeErase(phead->next);}
请在这里输入引用内容