速通数据结构与算法第四站双链表

系列文章目录

速通数据结构与算法系列

1   速通数据结构与算法第一站复杂度          http://t.csdnimg.cn/sxEGF

2   速通数据结构与算法第二站顺序表         http://t.csdnimg.cn/WVyDb

3   速通数据结构与算法第三站单链表          http://t.csdnimg.cn/cDpcC

感谢佬们支持！

系列文章目录

前言
一、双链表
0 结构体
1 接口声明
2 增加节点
3 初始化
4 打印
5 尾插
6 尾删
7 头插
8 头删
9 find
10 insert
11 erase
12 销毁
13 完整代码
二、OJ题
1 环形链表1
2 环形链表2
3 复杂链表的复制
三、链表和顺序表的对比&&补充deque
总结

前言

上篇博客我们探讨的是单链表，这篇博客将为大家带来双链表和3个更值得探讨的OJ题

双链表看似更复杂了，其实不然，代码写起来比单链表爽的多

我们要写的就是带头双向循环链表，这也是STL（SGI版）中list相同的结构

一、双链表

我们还是先来搞一个结构体

结构体

typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;

其中data表示数据，prev表示指向前一个结点，next表示指向后一个节点

接口声明

//增加节点
LTNode* BuyListNode(LTDataType x);//初始化
//void LTInit(LTNode**phead);
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);//判空
bool LTEmpty(LTNode* plist);//销毁
void LTDestroy(LTNode* phead);//尾插
void LTNodePushBack(LTNode* phead, LTDataType x);//尾删
void LTNodePopBack(LTNode* phead);//头插
void LTNodePushFront(LTNode* phead, LTDataType x);//头删
void LTNodePopFront(LTNode* phead);//find
LTNode* LTNodeFind(LTNode* phead, LTDataType x);//pos前插
void LTNodeInsert(LTNode* pos, LTDataType x);//删pos
void LTNodeErase(LTNode* pos);

增加节点

增加节点的逻辑简单，这里不再赘述

//创建节点
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

初始化

显然在双链表这里我们的初始化是有事做的，而不像单链表在使用时给个空就行

我们要创建哨兵位的头节点，还要让他的next和prev都指向自己（毕竟是个循环链表）

按理说这样修改头节点我们是要传二级指针的，但是后面的接口实际上都传一级指针就行，毕竟有了头节点，之后的修改都不涉及整个链表。

如果用了二级指针的写法，会是这样……

 void LTInit(LTNode* *phead)
{//哨兵位*phead = BuyListNode(-1);(*phead)->next = *phead;(*phead)->prev = *phead;}

用起来就是这样……

LTNode* plist = NULL;LTInit(&plist);

为了接口的一致性，我们也可以用传一级指针，只要用返回值带出来即可

//初始化
LTNode* LTInit()
{//哨兵位LTNode*phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;//返回头节点
}

用起来就是这样

	LTNode* plist = LTInit();

下来我们再写一下打印

打印

打印很简单，但是我们要控制好循环的逻辑，毕竟他是个循环链表，一不小心就会死循环

我可以定义一个cur指向phead->next,cur直到等于phead停下来

//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}
}

尾插

双链表的尾插相比于单链表轻松很多，首先它不用找尾（phead的prev就是尾），拿到尾以后我们只需改4个指针即可

如图所示

而且好消息是，我们通过画图发现，如果链表为空，上述逻辑依然成立，所以我们不用特判链表为空的情况

直接上代码

//尾插
void LTNodePushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//连接关系tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//空链表尾插不用单独处理。奈斯}

尾删

尾删只需考虑链表是否为空的情况即可，即我们不能删哨兵位的头节点

依然是改4个指针的问题

//尾删
void LTNodePopBack(LTNode* phead)
{assert(phead);//链表为空就不能再删assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* newtail = tail->prev;phead->prev = newtail;newtail->next = phead;free(tail);tail = NULL;}

头插

头插同样是改4个指针的逻辑

直接上代码

//头插
void LTNodePushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* head = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = head;head = newnode;}

头删

头删同理，我们只需额外判断链表是否为空就行

//头删
void LTNodePopFront(LTNode* phead)
{assert(phead);//链表为空就不能再删assert(!LTEmpty(phead));LTNode* head = phead->next;LTNode* newhead = head->next;newhead->prev = phead;phead->next = newhead;free(head);head = NULL;}

我们简单的做一波测试

LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 1);LTNodePushBack(plist, 4);LTNodePushBack(plist, 2);//LTNodePopBack(plist);LTNodePopBack(plist);LTNodePushBack(plist, 1);LTNodePushFront(plist, 3);LTPrint(plist);LTDestroy(plist);

（没有问题）

这里我们发现双链表的头插头删尾插尾删都是O（1），确实挺不错的

find

find的原理不用多说了，直接上代码

//寻找
LTNode* LTNodeFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}//找不见return NULL;
}

insert

我们要写的pos位置前插，在写了前面的之后，写这个就是砍瓜切菜啦~

只需额外判断pos是否合法即可

//pos位置前插入
void LTNodeInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* prev = pos->prev;newnode->next = pos;pos->prev = newnode;newnode->prev = prev;prev->next = newnode;
}

erase

/删pos位置
void LTNodeErase(LTNode* pos)
{assert(pos);assert(!LTEmpty(pos));LTNode* next = pos->next;LTNode* prev = pos->prev;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}

写了erase和insert之后，我们前面的代码就都不用写了，直接复用这个即可

尾插会是这样

//复用版本//LTNodeInsert(phead,x);

尾删

//复用版本//LTNodeErase(phead->prev);

头插

//复用版本//LTNodeInsert(phead->next,x);

头删

//复用版本//LTNodeErase(phead->next);

这样，如果面试官让你20min写一个链表，你直接写一个insert和erase就可以轻松搞定了

销毁

最后我们来搞定一下销毁就好啦！

//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);//由于传的是一级指针，记得要在外面手动置空
}

完整代码

完整代码是这样的…

list.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//增加节点
LTNode* BuyListNode(LTDataType x);//初始化
//void LTInit(LTNode**phead);
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);//判空
bool LTEmpty(LTNode* plist);//销毁
void LTDestroy(LTNode* phead);//尾插
void LTNodePushBack(LTNode* phead, LTDataType x);//尾删
void LTNodePopBack(LTNode* phead);//头插
void LTNodePushFront(LTNode* phead, LTDataType x);//头删
void LTNodePopFront(LTNode* phead);//find
LTNode* LTNodeFind(LTNode* phead, LTDataType x);//pos前插
void LTNodeInsert(LTNode* pos, LTDataType x);//删pos
void LTNodeErase(LTNode* pos);

list.c

#include"List.h"//创建节点
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}#if 0
//初始化(二级指针z)
void LTInit(LTNode* *phead)
{//哨兵位*phead = BuyListNode(-1);(*phead)->next = *phead;(*phead)->prev = *phead;//return phead;//返回头节点}
#endif//初始化
LTNode* LTInit()
{//哨兵位LTNode*phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;//返回头节点
}
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}
}//判空
bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);//由于传的是一级指针，记得要在外面手动置空
}//尾插
void LTNodePushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//连接关系tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//空链表尾插不用单独处理。奈斯//复用版本//LTNodeInsert(phead,x);
}//尾删
void LTNodePopBack(LTNode* phead)
{assert(phead);//链表为空就不能再删assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* newtail = tail->prev;phead->prev = newtail;newtail->next = phead;free(tail);tail = NULL;//复用版本//LTNodeErase(phead->prev);
}//头插
void LTNodePushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* head = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = head;head = newnode;//复用版本//LTNodeInsert(phead->next,x);
}//头删
void LTNodePopFront(LTNode* phead)
{assert(phead);//链表为空就不能再删assert(!LTEmpty(phead));LTNode* head = phead->next;LTNode* newhead = head->next;newhead->prev = phead;phead->next = newhead;free(head);head = NULL;//复用版本//LTNodeErase(phead->next);
}//寻找
LTNode* LTNodeFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}//找不见return NULL;
}//pos位置前插入
void LTNodeInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* prev = pos->prev;newnode->next = pos;pos->prev = newnode;newnode->prev = prev;prev->next = newnode;
}//删pos位置
void LTNodeErase(LTNode* pos)
{assert(pos);assert(!LTEmpty(pos));LTNode* next = pos->next;LTNode* prev = pos->prev;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}

test.c

#include"List.h"void test1()
{//LTNode* plist = NULL;// LTInit(&plist);LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 1);LTNodePushBack(plist, 4);LTNodePushBack(plist, 1);LTNodePushBack(plist, 2);//LTNodePopBack(plist);//LTNodePopBack(plist);LTNodePushFront(plist, 3);LTNode* ret = LTNodeFind(plist, 4);LTNodeErase(ret);LTPrint(plist);LTDestroy(plist);plist = NULL;
}void test2()
{LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 1);LTNodePushBack(plist, 4);LTNodePushBack(plist, 2);//LTNodePopBack(plist);LTNodePopBack(plist);LTNodePushBack(plist, 1);LTNodePushFront(plist, 3);LTPrint(plist);LTDestroy(plist);
}int main()
{test2();return 0;
}

二、OJ题

这次我们来看几道相对较难的OJ题

1 环形链表1

题目链接： . - 力扣（LeetCode）

首先这个题最好不要遍历，不然会很容易死循环

最简单的方法是快慢指针，让slow一次走一步，fast一次走两步，如果他们最终相遇

说明有环

为什么呢？

1 显然，slow和fast的相对速度是1步（1个节点），由物理学知识我们知道，如果有环，他们最终一定相遇，不会错过

2 如果fast一次走3步呢？相对速度就会是2步，suppose slow进环后fast开始追击。如果他们之间的距离是偶数，他们就会相遇；如果是奇数便会错过。以此类推。

代码还是简单的，我们很轻松就能写出来啦~

bool hasCycle(struct ListNode* head)
{//快慢指针，追击相遇struct ListNode* fast = head;struct ListNode* slow = head;//fast一次两步，slow一次一步while (fast && fast->next)//如果不断言fast，测试用例会有空链表,如果不想断言fast，可以加上面的那个判断{slow = slow->next;fast = fast->next->next;if (slow == fast){return true;}}return false;
}

2 环形链表2

题目链接： . - 力扣（LeetCode）

下来恶心的是环形链表2，它建立在环形链表1的基础上

我们需要在有环的基础上找到环的入口节点

先说结论，再证明：在环形链表1中我们可以得到最后slow和fast的相遇点（如果有环的话）

现在是这样，我们再给两个指针，一个从链表开始走，另一个从相遇点走，他们最后相遇的节点

就是我们要的入口节点。

证明：

suppose入口点到环的起点距离为N，环的长度为C，入口点至相遇点的距离为x

也就是这样……

首先在相遇时slow走的距离为：N+X

fast走的距离为：N+X+n*C（n为fast走的圈数）

由于fast的距离==slow的两倍

即2*（N+X）=N+X+n*C

化简一下就会得到

N+X=n*C

N=n*C-X

由此便得：此时再用两个指针，一个从链表开始走，另一个从相遇点走，他们最后相遇的节点

就是我们要的入口节点。

代码如下……

bool hasCycle(struct ListNode* head)
{//快慢指针，追击相遇struct ListNode* fast = head;struct ListNode* slow = head;//fast一次两步，slow一次一步while (fast && fast->next)//如果不断言fast，测试用例会有空链表,如果不想断言fast，可以加上面的那个判断{slow = slow->next;fast = fast->next->next;if (slow == fast){return true;}}return false;
}struct ListNode* detectCycle(struct ListNode* head)
{if (hasCycle(head) == NULL){return NULL;}else{//一个从相遇点开始走，一个从头走，它们会在环的入口相遇struct ListNode* meet = hasCycle(head);while (meet != head){meet = meet->next;head = head->next;}return meet;}
}

我们还有第二种思路

在相遇点处断开，我们会得到两条链表，如图

我们可以求这两条链表的相交节点（具体相交链表的逻辑请大家移步我的上一篇博客

（ http://t.csdnimg.cn/cDpcC）

//链表相交
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{int lenA = 1;int lenB = 1;struct ListNode* tailA = headA;struct ListNode* tailB = headB;while (tailA){lenA++;tailA = tailA->next;}while (tailB){lenB++;tailB = tailB->next;}//如果相交，尾节点一定相同  //这个条件很有必要if (tailA != tailB){return NULL;}//快的先走差距步，再一起走struct ListNode* fast = lenA > lenB ? headA : headB;struct ListNode* slow = lenA > lenB ? headB : headA;int gap = abs(lenA - lenB);while (gap--){fast = fast->next;}while (fast != slow){fast = fast->next;slow = slow->next;}return fast;}
struct ListNode* hasCycle(struct ListNode* head)
{//快慢指针，追击相遇struct ListNode* fast = head;struct ListNode* slow = head;//fast一次两步，slow一次一步while (fast && fast->next)//如果不断言fast，测试用例会有空链表,如果不想断言fast，可以加上面的那个判断{slow = slow->next;fast = fast->next->next;if (slow == fast){return slow;}}return NULL;
}struct ListNode* detectCycle(struct ListNode* head)
{if (hasCycle(head) == NULL){return NULL;}else{struct ListNode* newhead = hasCycle(head)->next;hasCycle(head)->next = NULL;return getIntersectionNode(newhead, head);}
}

3 复杂链表的复制

题目链接：. - 力扣（LeetCode）

首先，这个题很离谱，很难，算是大家目前链表学习的最后一块天花板

我们要复制一个带有random指针得链表，其中random会指向任意节点，这道题的关键就是

如何让新链表的random指针指向新链表的节点而非老链表的节点。

学过C++的兄弟们肯定就爽了，直接哈希启动！

构建源节点和新节点的映射关系就行，确实，哈希真的很香，这里放一份参考代码

class Solution {
public:Node* copyRandomList(Node* head) {if(head==nullptr)return nullptr;unordered_map<Node*,Node*> m;Node*cur=head;while(cur){//建立旧结点和新节点的链接m[cur]=new Node(cur->val);cur=cur->next;}cur=head;while(cur){m[cur]->next=m[cur->next];m[cur]->random=m[cur->random];cur=cur->next;}return m[head];}};

但是现在我们在学数据结构，没有哈希表，这怎么办?

这个时候有大佬就想了一种办法，在每个原节点的后面拷贝这个节点，并链接至源节点之后

就像这样……

这有什么用呢？

别忘了我们的核心问题是解决新节点random的问题，此时我们会发现，

新节点的random==老节点random的next，

这波还是非常神奇的，一气呵成，行云流水，让人拍案叫绝。

接下来就是将这些新节点串成一个新链表，并将老链表恢复原样的工作，看似简单，但代码其实并不好写

代码如下~

struct Node* copyRandomList(struct Node* head)
{if (head == NULL)return NULL;struct Node* cur = head;//1 每个节点后连一个拷贝后的节点while (cur){struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));newnode->val = cur->val;struct Node* next = cur->next;cur->next = newnode;newnode->next = next;cur = next;}cur = head;while (cur){struct Node* newnode = cur->next;if (cur->random == NULL){newnode->random = NULL;}else{newnode->random = cur->random->next;}//一次走两步！cur = cur->next->next;}//链接成新链表，cur = head;struct  Node* newhead;struct  Node* tail;while (cur){struct Node* copy = cur->next;struct Node* next = copy->next;if (NULL == newhead){tail = newhead = copy;}else{tail->next = copy;tail = tail->next;}//恢复原链表cur->next - next;cur = next;}return newhead;
}

三、链表和顺序表的对比&&补充deque

话不多说我们直接上一个表格

不同点	顺序表	链表
存储空间	物理上一定连续	物理上不一定连续
随机访问	O（1）	O（n）
随意位置插入删除元素	可能要挪元素，O（n）	只需修改指针指向
插入	动态顺序表须扩容	没有容量的概念
迭代器失效	有	无
应用场景	随机访问和元素高效存储	任意位置插入删除频繁
缓存利用率	高	低