面试官：给你十分钟，写出可以增删查改任意位置插入删除的链表！
我有一个师兄，前几年去面试，笔试过了，到了面试环节，面试官提出了一个让他觉得面试官在为难他的一个问题：给你十分钟，写出可以增删查改任意位置插入删除的链表！
当时他一下子感觉这是不可能的，因为众所周知——链表的接口有初始化、打印、头插、头删、尾插、尾删、中间插入、中间删除、查找等这么多接口函数，看这些名字就知道把这些写完需要不少时间。
师兄说，他最快也要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）运行代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 | ListNode* ListNodeFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while(cur != phead) { if(cur->data == x) returncur; cur = cur->next; } returnNULL; } |
查找后返回的是结点的指针，可以用==pos->data=某个数==进而修改这个点的值！！！
（2）运行结果：
9.双向链表的中间插入：
（1）运行代码：
插入在指定位置的前面
| 1 2 3 4 5 6 7 8 9 10 | voidListNodeInsert(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）运行代码：
| 1 2 3 4 5 6 7 8 9 10 | voidListNodeErase(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.双向链表的销毁：
每一次用完链表后销毁是很有必要的，如果不销毁，将会导致==内存的泄露==，短时间内可能没用什么，且很难被发现，但时间长了，必将导致==程序的崩溃==，最终将导致时间和金钱的浪费！！！
这里介绍两种销毁：
方法一：销毁全部，不保留头结点：
方法二：保留头结点：
具体选择哪一种，需要看==实际需要==！！！
12.完整代码：
（1）List.h文件：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef intLTDataType; typedef struct ListNode { struct ListNode* prev; LTDataType data; struct ListNode* next; }ListNode; ListNode* ListNodeBuy(LTDataType x); voidListNodeInit(ListNode** pphead); voidListPrint(ListNode* phead); voidListNodePushBack(ListNode* phead, LTDataType x); voidListNodePopBack(ListNode* phead); voidListNodePushFront(ListNode* phead, LTDataType x); voidListNodePopFront(ListNode* phead); ListNode* ListNodeFind(ListNode* phead, LTDataType x); voidListNodeInsert(ListNode* pos, LTDataType x); voidListNodeErase(ListNode* pos); voidListNodeDestroy(ListNode* phead); |
（2）List.c文件：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 | #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; returnnewnode; } voidListNodeInit(ListNode** pphead) { *pphead = ListNodeBuy(0); (* pphead)->next = *pphead; (*pphead)->prev = *pphead; } ListNode* ListNodeInit() { ListNode* phead = ListNodeBuy(0); phead->next = phead; phead->prev = phead; returnphead; } voidListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while(cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } voidListNodePushBack(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; } voidListNodePopBack(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; } voidListNodePushFront(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; } voidListNodePopFront(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) returncur; cur = cur->next; } returnNULL; } voidListNodeInsert(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; } voidListNodeErase(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; } voidListNodeDestroy(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 intmain(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); return0; } |
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);}
请在这里输入引用内容
最后如果有时间，记得写上销毁函数，可以反映你有一定的项目经验，知道要销毁链表，防止内存泄***r>祝愿大家都可以拿到自己心仪的offer，成为offer收割机！！！