目录
1. 双向循环链表（带哨兵位）
2.1 双链表结构
2.2 创建双链表结点
2.3 初始化双链表
2.4 尾插
2.5 尾删
2.6 头插
2.7 头删
2.8 在pos的前面进行插入
2.9 删除pos位置的节点
2.10 打印双向链表
3.1 双链表代码仓库
4.1 环形链表
4.2 环形链表 II
4.3 相交链表
4.4 复制带随机指针的链表
1. 双向循环链表（带哨兵位）
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
2.1 双链表结构
注意事项：
1.定义两个指针分别指向头和尾
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}ListNode;
2.2 创建双链表结点
注意事项：
1.malloc记得判空
2.初始化newnode内的指针
ListNode* ListCreate(LTDataType x)//创建双链表结点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc:fail");
exit(-1);
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
2.3 初始化双链表
注意事项：
1.让头结点的next和prev指向自己
ListNode* ListInit()
{
ListNode* pphead = ListCreate(-2);
pphead->next = pphead;
pphead->prev = pphead;
return pphead;
}
2.4 尾插
注意事项：
1.头结点的prev就是尾，找到尾后修改尾的next，修改newnode的prev和next，和无效头结点phead的prev （看图写代码）
void ListPushBack(ListNode* pHead, LTDataType x)//尾插
{
assert(pHead);
ListNode* newnode = ListCreate(x);
ListNode* tail = pHead->prev;//找到尾
//双链表的链接
tail->next = newnode;
newnode->prev = tail;
pHead->prev = newnode;
newnode->next = pHead;
}
2.5 尾删
注意事项：
1.注意控制边界，不要删除无效头结点
2.记录尾删结点和尾删节点的前一个，这样顺序便不重要
void ListPopBack(ListNode* pHead)//双链表尾删
{
assert(pHead);
assert(pHead->next != pHead);
ListNode* del = pHead->prev;
ListNode* prevdel = del->prev;
prevdel->next = pHead;
pHead->prev = prevdel;
free(del);
ListErase(pHead->prev);
}
2.6 头插
注意事项：
1.记录phead->next，变成phead newnode cur的链接顺序
void ListPushFront(ListNode* pHead, LTDataType x)// 双向链表头插
{
assert(pHead);
ListNode* newnode = ListCreate(x);
ListNode* cur = pHead->next;
//pHead newnode cur
newnode->next = cur;
newnode->prev = newnode;
pHead->next = newnode;
cur->prev = newnode;
}
2.7 头删
注意事项：
1.1.注意控制边界，不要删除无效头结点
void ListPopFront(ListNode* pHead)//双向链表头删
{
assert(pHead);
assert(pHead->next != pHead);
ListNode* cur = pHead->next->next;
ListNode* prevcur = pHead->next;
pHead->next = cur;
cur->prev = pHead;
free(prevcur);
}
2.8 在pos的前面进行插入
注意事项：
1.本质是对prev newnode pos三个链接操作
void ListInsert(ListNode* pos, LTDataType x)//双向链表在pos的前面进行插入
{
assert(pos);
ListNode* newnode = ListCreate(x);
ListNode* prev = pos->prev;
//prev newnode pos
pos->prev = newnode;
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
}
2.9 删除pos位置的节点
void ListErase(ListNode* pos)//双向链表删除pos位置的节点
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
2.10 打印双向链表
注意事项
1.phead->next !=phead 便是限制条件
void ListPrint(ListNode* pHead)//打印链表
{
assert(pHead);
ListNode* cur = pHead->next;
while(cur != pHead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("n");
}
3.1 双链表代码仓库
每日刷题: 刷题 - Gitee.com
4.1 环形链表
思路：
1.快慢指针，快指针一次走两步，慢指针一次走一步。快指针进环后开始循环，慢指针再进后，慢指针最多走两圈，快指针一定会追上
bool hasCycle(struct ListNode *head) {
struct ListNode*slow=head;
struct ListNode*fast=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}
4.2 环形链表 II
思路：
1.让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行（环形链表），两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
2.设E为入环点，H到E的距离为L，M是快慢指针入环后相交的交点，设E到M之间的距离为X，设环的距离为R，M到E的距离为R-X
则慢指针走的路程：X+L，快指针走的路程：NR+L+X，由于快指针走的路程是慢指针的两倍，得出公式：2（X+L）=NR+L+X
化简后：X+L=NR
L=NR-X,假设R为1，L=R-X，既一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast=head,*slow=head;
while(fast &&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
struct ListNode*meet=slow;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return NULL;
}
4.3 相交链表
思路：
1.两个链表之间，相交后的长度是相同的，只需要减去A链表和B链表，让长链表走绝对值步，在一起走即可找到相交结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *slow=headA;
struct ListNode *fast=headB;
int countA=0,countB=0;
while(slow)
{
slow=slow->next;
countA++;
}
while(fast)
{
fast=fast->next;
countB++;
}
if(fast!=slow)
{
return NULL;
}
//相交的情况
struct ListNode*shortlist=headA,*longlist=headB;
if(countA>countB)
{
shortlist=headB;
longlist=headA;
}
int gap=abs(countA-countB);//求绝对值
while(gap--)
{
longlist=longlist->next;
}
while(longlist !=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}
4.4 复制带随机指针的链表
思路：
本期难点在于如何拷贝random，并且不能让原链表和复制链表相交
1.拷贝一份新链表，每一个结点尾插到原链表的后面
2.让复制链表的random指向原链表random的next（原链表后面便是复制链表）
3.分离复制链表
struct Node* copyRandomList(struct Node* head) {
//1.创建复制链表，尾插在后面
struct Node*cur=head;
while(cur)
{
struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
struct Node*next=cur->next;
newnode->val = cur->val;
newnode->next=next;
cur->next=newnode;
cur=next;
}
//2.让random链接
cur=head;
while(cur)
{
struct Node*copy=cur->next;
if(cur->random == NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
//3.分开链表，返回新链表头节点
cur=head;
struct Node*pHead=(struct Node*)malloc(sizeof(struct Node));
pHead->next=NULL;
struct Node* Nhead=pHead;
while(cur!=NULL &&cur->next != NULL)
{
pHead->next=cur->next;
pHead=pHead->next;
cur->next=pHead->next;
cur=cur->next;
}
return Nhead->next;
}
