前言：
为了更好地理解本节，建议先阅读： 数据结构 - c语言链表操作
实际中要实现的链表的结构非常多样，以下情况组合起来有多种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
解读：
带头：
存在一个哨兵位的节点，该节点不存储任何有效数据，属于无效节点，但通过这个无效节点当头节点让我们在某些方面使用会有一些优势。
双向：
指的是节点中不再只有一个指针，而是有两个指针，一个指向前一个节点，另一个指向后一个节点。
循环：
尾指针不再指向NULL，而是指向头节点。
然而，现实中实用的只有两种：分别是无头单向非循环链表；带头双向循环链表。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外，这个结构虽然结构复杂，但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口，insert 和 earse 头尾的插入和删除就可以搞定了！
双链表的定义与接口函数
定义双链表
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode;
接口函数
void ListPrint(LTNode* phead); //void ListInit(LTNode** pphead); LTNode* ListInit(); LTNode* BuyLTNode(LTDataType x); void ListPushBack(LTNode* phead, LTDataType x); void ListPopBack(LTNode* phead); void ListPushFront(LTNode* phead, LTDataType x); void ListPopFront(LTNode* phead); LTNode* ListFind(LTNode* phead, LTDataType x); // 在pos之前插入 void ListInsert(LTNode* pos, LTDataType x); //void ListInsert(int i, LTDataType x); // 删除pos位置的节点 void ListErase(LTNode* pos); void ListDestory(LTNode* phead);
详解接口函数的实现
创建新节点（BuyLTNode）
LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
初始化双链表（ListInit）
LTNode* ListInit() { LTNode* phead = BuyLTNode(0); phead->next = phead; phead->prev = phead; return phead; }
这里我们使用 BuyLTNode 函数开辟一块空间作为 "哨兵位" pHead ，最后将其进行一个初始化。最后再将 pHead 作为结果返回回去，外面就可以接收到了。这就是返回值的方法，当然这里也可以采用二级指针的方法来完成。
双向链表打印（ListPrint）
void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n\n"); }
双链表查找（ListFind）
LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
双链表销毁（ListDestory）
void ListDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; //ListErase(cur); free(cur); cur = next; } free(phead); //phead = NULL; }
1、双链表pos位置之前插入（ListInsert）
void ListInsert(LTNode* pos, LTDataType x) { assert(pos); /*LTNode* newnode = BuyLTNode(x); pos->prev->next = newnode; newnode->prev = pos->prev; pos->prev = newnode; newnode->next = pos;*/ LTNode* newnode = BuyLTNode(x); LTNode* posPrev = pos->prev; newnode->next = pos; pos->prev = newnode; posPrev->next = newnode; newnode->prev = posPrev; }
非常简单，假设d2是新节点，就是让新节点的两条链接在d3上，然后把d1的两条链接新节点上
2、双链表删除pos位置（ListEarse）
void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; free(pos); pos = NULL; prev->next = next; next->prev = prev; }
假设要删除d2，那么只需要直接把d1的两条链接d3上即可
3、双向链表尾插（ListPushBack）
void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyLTNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
4、双向链表头插（ListPushFront）
void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); }
5、双链表头删（ListPopFront）
void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); ListErase(phead->next); }
6、双链表尾删（ListPopBack）
void ListPopBack(LTNode* phead) { assert(phead); // 链表为空 assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tail = NULL; tailPrev->next = phead; phead->prev = tailPrev; }
总结：
用ListInsert和ListEarse的复用优化后：
void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead, x); } void ListPopBack(LTNode* phead) { assert(phead); // 链表为空 assert(phead->next != phead); ListErase(phead->prev); } void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); ListErase(phead->next); } void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); }
所以，双向链表严格来说只需要快速地实现 insert 和 earse 这两个接口就可以搞定了。如果以后让你快速实现一个双向链表，你把 "pos位置之前插入" 和 "删除pos位置" 这两个接口写好，头尾的插入和删除直接复用就可以搞定了。
完整代码
List.h
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; void ListPrint(LTNode* phead); //void ListInit(LTNode** pphead); LTNode* ListInit(); LTNode* BuyLTNode(LTDataType x); void ListPushBack(LTNode* phead, LTDataType x); void ListPopBack(LTNode* phead); void ListPushFront(LTNode* phead, LTDataType x); void ListPopFront(LTNode* phead); LTNode* ListFind(LTNode* phead, LTDataType x); // 在pos之前插入 void ListInsert(LTNode* pos, LTDataType x); //void ListInsert(int i, LTDataType x); // 删除pos位置的节点 void ListErase(LTNode* pos); void ListDestory(LTNode* phead);
List.c
#include"List.h" LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n\n"); } //void ListInit(LTNode** pphead) //{ // assert(pphead); // *pphead = BuyLTNode(0); // (*pphead)->next = *pphead; // (*pphead)->prev = *pphead; //} LTNode* ListInit() { LTNode* phead = BuyLTNode(0); phead->next = phead; phead->prev = phead; return phead; } void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); //LTNode* tail = phead->prev; //LTNode* newnode = BuyLTNode(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); } void ListPopBack(LTNode* phead) { assert(phead); // 链表为空 assert(phead->next != phead); /* LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tail = NULL; tailPrev->next = phead; phead->prev = tailPrev;*/ ListErase(phead->prev); } void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); ListErase(phead->next); } void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); } LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void ListInsert(LTNode* pos, LTDataType x) { assert(pos); /*LTNode* newnode = BuyLTNode(x); pos->prev->next = newnode; newnode->prev = pos->prev; pos->prev = newnode; newnode->next = pos;*/ LTNode* newnode = BuyLTNode(x); LTNode* posPrev = pos->prev; newnode->next = pos; pos->prev = newnode; posPrev->next = newnode; newnode->prev = posPrev; } // 驼峰法 // 函数和类型所有单词首字母大写 // 变量：第一个单词小写后续单词首字母大写 void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; free(pos); pos = NULL; prev->next = next; next->prev = prev; } void ListDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; //ListErase(cur); free(cur); cur = next; } free(phead); //phead = NULL; } ------------------------------------------------------------------------------ #include "List.h" ListNode* BuyListNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->data = x; node->next = NULL; node->prev = NULL; return node; } ListNode* ListCreate() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); head->next = head; head->prev = head; return head; } void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; while (cur != pHead) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); } void ListDestroy(ListNode* pHead) { ListNode* cur = pHead->next; while (cur != pHead) { ListNode* next = cur->next; free(cur); cur = next; } free(pHead); } void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); //ListNode* newnode = BuyListNode(x); phead tail newnode //ListNode* tail = pHead->prev; //tail->next = newnode; //newnode->prev = tail; //newnode->next = pHead; //pHead->prev = newnode; ListInsert(pHead, x); } void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); //ListNode* newnode = BuyListNode(x); //ListNode* first = pHead->next; //pHead->next = newnode; //newnode->prev = pHead; //newnode->next = first; //first->prev = newnode; /*ListNode* newNode = BuyListNode(x); newNode->next = pHead->next; pHead->next->prev = newNode; pHead->next = newNode; newNode->prev = pHead;*/ ListInsert(pHead->next, x); } void ListPopBack(ListNode* pHead) { assert(pHead); //ListNode* tail = pHead->prev; //ListNode* tailPrev = tail->prev; pHead tailPrev tail //tailPrev->next = pHead; //pHead->prev = tailPrev; //free(tail); /*ListNode* tail = pHead->prev; pHead->prev = tail->prev; tail->prev->next = pHead; free(tail);*/ ListErase(pHead->prev); } void ListPopFront(ListNode* pHead) { //... ListErase(pHead->next); } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); // prev newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }
链表OJ练习巩固
138. 复制带随机指针的链表 - 力扣（LeetCode）
解题思路：
此题可以分三步进行：
1.拷贝链表的每一个节点，拷贝的节点先链接到被拷贝节点的后面
2.复制随机指针的链接：拷贝节点的随机指针指向被拷贝节点随机指针的下一个位置
3.拆解链表，把拷贝的链表从原链表中拆解出来
class Solution { public: Node* copyRandomList(Node* head) { // 1.拷贝链表，并插入到原节点的后面，如图1 Node* cur = head; while(cur) { Node* next = cur->next; Node* copy = (Node*)malloc(sizeof(Node)); copy->val = cur->val; // 插入 cur->next = copy; copy->next = next; // 迭代往下走 cur = next; } // 2.置拷贝节点的random，如图2 cur = head; while(cur) { Node* copy = cur->next; if(cur->random != NULL) copy->random = cur->random->next; else copy->random = NULL; cur = copy->next; } // 3.解拷贝节点，链接拷贝节点，如图3 Node* copyHead = NULL, *copyTail = NULL; cur = head; while(cur) { Node* copy = cur->next; Node* next = copy->next; // copy解下来尾插 if(copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copy; } cur->next = next; cur = next; } return copyHead; } };
图1：
图2：
图3：
