目录
1.顺序表&双向循环链表的优点和缺点
顺序表：
一.优点：
- 尾插尾删效率很高
- 支持用下标随机访问
二.缺点：
- 头部和中部插入和删除效率低O(n)
- 扩容-----性能消耗+空间消耗
双向循环链表：
一.优点：
- 任意位置插入删除效率很高O(1)
- 按需申请释放
二.缺点:
- 不支持随机访问
综合而言，两个各有优缺，相辅相成，具体用谁看场景，但是总体而言顺序表使用的频率更高一点
扩展一点：
顺序表的cpu高速缓存命中率高（顺序表空间连续）
?
2.单链表和双向循环链表
1.单链表：其他结构的子结构（比如哈希桶），面试经常问到和OJ题目，且只适合头部的插入删除。
2.双向循环链表：结构复杂，但是实现简单，最为实用，常被用于实际存数据，适合任意位置的插入删除。
3.一点杂七杂八的东西
3-1顺序表和链表打印的断言
1.顺序表和链表打印断言
顺序表定义：SeqList Sq;
在传给打印函数的时候:SeqListPrint(&Sq)
在函数内部的时候&Sq一定不为空，void SeqListPrint(SeqList* ps)所以要断言一下assert(ps);
单链表定义变量: SLTNode* phead;
在传给打印函数的时候:SLTNodePrint(&phead);
在函数内部打印的时候phead为空的时候，&phead也可能为空，所以不能断言
但是注意：虽然phead为空，但是pphead不为空?，所以在链表头插函数内部还是要对pphead断言。
原因：phead没有指向任何内容，但是phead本身是一个指针变量，是变量就有地址。
?
3-2.栈上和堆上定义一个新节点?
2.栈（错）和堆上（对）定义一个新节点
void SLTNodePushFront(SLTNode** pphead,STDateType x)
{
//错误示范：栈上开辟的，出函数销毁
SLTNode newnode;
//正确做法：malloc结点，堆上开辟，空间需要手动释放
SLTNode* newhead=(SLTNode*)malloc(sizeof(SLTNode));
}3-3.二级指针?
我们在主函数定义了SListNode*? plist;
在改变plist的指向的时候就要传二级指针，但是如果在函数内改结点，直接用一级指针就能改，就像我们在函数内部定义的prev,cur等。这也就是哨兵位头结点的原理，在因为有哨兵位的头结点，就不用改plist，所以可以在主函数内传一级指针。
3.二级指针
以尾插函数为例，如果主函数里的plist为空，那么要改plist就要传二级指针
但是为什么在plist不为空的时候，要尾插一个
void SLTNodePushBack(SLTNode* pphead, SLTDateType x)//1
{
assert(pphead);//2
SLTNode* newhead = (SLTNode*)malloc(sizeof(SLTNode));
newnode->next = NULL;
newnode->date = x;
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail)
{
tail = tail->next;
}
tail->next = newnode;//3
}
}无头单向不循环链表传二级指针发挥作用的情况：
- 没有结点尾插
- 只有一个结点尾删
- 头插
- 头删
- 销毁
3-4.哨兵头结点的作用
头结点的作用：
- 方便对plist为空等特殊情况时的统一操作
- 避免传二级指针
备注：有人说哨兵位头结点的数据域是用来存储单链表的长度；
专业打假：其实这种说法是错误的，因为结点的数据域为char类型的且链表长度大于127的时候就会溢出，所以这种说法是错误的。
3-5?为什么单链表的基本操作中无tail记录尾
看过我写题的应该知道，在建立新链表的时候，通常是采用尾插操作，尾插相对于头插能够保证新链表的结点在原链表的相对顺序不变，但是尾插的缺点是每次尾插都要找尾，所以我们定义一个尾指针，实时更新尾指针。
那为什么单链表的基本操作中无tail记录尾？那是因为在基本操作中不止有尾插，还有尾删，定义一个tail效果适用性不是很强。
4.替换法删除pos结点
?
基于单链表删除pos位置还要找尾的麻烦，删除pos位置的结点有一个替换法删除，数据域值交换的方法，时间复杂度是O(1):
如果要删除pos位置的结点，则可以狸猫换太子把pos后面一个结点的值给pos位置的数据域，然后pos->next=pos->next->next,也就是把pos后面那个结点作替死鬼。
缺点：pos位置不能是尾结点。
pos位置是尾结点且链表是循环链表就可以，但是如果是循环链表的话就没必要使用替换法删除pos位置的结点.
4-1.变式
如果要在pos位置之前插入一个结点，时间复杂度为O(1),也可以采用这种方法：
BuySListNode(pos->val);
pos->val=x;
5 .链表调试
当OJ写不出来，想在VS上调试代码，找Bug，但是每次还要重建链表？有什么解决办法？
备注：程序员一半的时间都在改Bug,你连调试都不会，就等着扣绩效吧😁😁
解决办法：在桌面上备份一份单链表的代码，方便OJ调试。（代码如下）
#define _CRT_SECURE_NO_WARNINGS 1
struct ListNode
{
int val;
struct ListNode* next;
};
#include<stdio.h>
#include<stdlib.h>
int main()
{
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
n1->val = 1;
n2->val = 2;
n3->val = 3;
n4->val = 4;
n5->val = 5;
n6->val = 6;
n7->val = 7;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = n7;
n7->next = NULL;
return 0;
}6.为什么学校老师讲的时候不先讲带头结点的
- 实际应用中很少带头
- OJ题的head大大部分都是不带头的
7.刷刷刷题
上次的链表题刷的过瘾吗？链表习题集1
我又双叒叕来了，记住题目是环环相扣的，记得先把习题集1做了哦，有些解法这里用到将不会再细讲...，敬请谅解?
7-1.回文链表
?思路1：
- 第一步：利用快慢指针找到链表的中间结点slow
- 第二步：将中间结点开始以后的结点部分逆置(反转），得到相交链表的新头指针prev
- 第三步：遍历判断两个链表是否值相等
反转过程是最重要的部分，这里给出一点图理解一下
class PalindromeList {
public:
bool chkPalindrome(ListNode* phead) {
// 第一步：快慢指针求中间结点slow
struct ListNode* fast,*slow;
fast=slow=phead;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
//第二步:部分反转,得新头结点prev
struct ListNode* prev=NULL;
struct ListNode* cur=slow;
while(cur)
{
struct ListNode* next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
//第三步：判断新旧链表是否相等
struct ListNode* newhead=prev;
struct ListNode* oldhead=phead;
while(newhead)
{
if(newhead->val!=oldhead->val)
{
return false;
}
newhead=newhead->next;
oldhead=oldhead->next;
}
return true;
}
};这里其实形参名是可以改成自己喜欢的名字，而不是题目这么挫的A?
思路2：牢牢抓住回文链表的定义，从前往后和从后往前读都是一样的
- 第一步：拷贝原链表，得到头指针copyhead
- 第二步：将原链表整体反转,得到r头指针eversehead
- 第三步：遍历判断两个链表是否值相等
（备注：这里一定一定要记得先拷贝一份原链表，否则反转后得到的链表将不再是原先那个链表！）
class PalindromeList {
public:
//动态开辟一个新节点，新节点的值为cur->val
struct ListNode* BuySListNode(int val)
{
struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
newnode->val=val;
newnode->next=NULL;
return newnode;
}
bool chkPalindrome(ListNode* phead) {
//第一步：拷贝原链表，得到copyhead
struct ListNode* Guard,*Tail;
Guard=Tail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=phead;
while(cur)
{
struct ListNode* next=cur->next;
struct ListNode* newnode=BuySListNode(cur->val);
Tail->next=newnode;
Tail=Tail->next;
cur=next;
}
struct ListNode* copyhead=Guard->next;
free(Guard);
Guard=NULL;
//第二步：将原链表整体反转,得到reversehead
struct ListNode* prev=NULL;
struct ListNode* cur2=phead;
while(cur2)
{
struct ListNode* next=cur2->next;
cur2->next=prev;
prev=cur2;
cur2=next;
}
struct ListNode* reversehead=prev;
//第三步：遍历判断两个链表是否值相等
while(copyhead)
{
if(copyhead->val!=reversehead->val)
{
return false;
}
copyhead=copyhead->next;
reversehead=reversehead->next;
}
return true;
}
};7-2.相交链表
题目的相交链表可能有的同学会误以为是X字形，但是却只有Y字形，原因是每一个结点只有一个指针域，没有两个指针域。?
思路：
- 第一步：分别遍历两个链表，分别求出两个链表的长度
- 第二步：让长度长的那个链表先走两链表长度的差距步
- 第三步：短链表从头开始走，长链表从差距步开始同步走
- 第四步：相遇点即是相交链表的交点结点，返回
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//第一步：分别遍历两个链表，分别求出两个链表的长度
int lenA=1,lenB=1;
struct ListNode* TailA=headA;
struct ListNode* TailB=headB;
while(TailA->next)
{
++lenA;
TailA=TailA->next;
}
while(TailB->next)
{
++lenB;
TailB=TailB->next;
}
if(TailA!=TailB)
{
return false;
}
//第二步：让长度长的那个链表先走两链表长度的差距步
struct ListNode* longhead=headA;
struct ListNode* shorthead=headB;
if(lenA<lenB)
{
longhead=headB;
shorthead=headA;
}
int div=abs(lenA-lenB);
struct ListNode* cur1=longhead;
struct ListNode* cur2=shorthead;
while(div--)
{
cur1=cur1->next;
}
//第三步：短链表从头开始走，长链表从差距步开始同步走
while(cur1!=cur2)
{
cur1=cur1->next;
cur2=cur2->next;
}
//第四步：相遇点即是相交链表的交点结点，返回
return cur1;
}7-3.?链表分割
思路：将链表结点按数据值<x和>=x尾插到相应链表?，然后再将两分割的链表连接起来。
- 第一步：定义大小Guard和Tail指针
- 第二步:? ?遍历尾插到相应新链表
- 第三步： 连接两个分割的链表
备注：记得将bigTail->next置空！！！否则会运行超时
class Partition {
public:
ListNode* partition(ListNode* pHead, int val) {
// write code here
//第一步：定义大小Guard和Tail指针
struct ListNode* lessGuard,*lessTail;
lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
lessGuard->next=NULL;
struct ListNode* bigGuard,*bigTail;
bigGuard=bigTail=(struct ListNode*)malloc(sizeof(struct ListNode));
bigGuard->next=NULL;
//第二步:? ?遍历尾插到相应新链表
struct ListNode* cur=pHead;
while(cur)
{
struct ListNode* next=cur->next;
if(cur->val<val)
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
bigTail->next=cur;
bigTail=bigTail->next;
}
cur=next;
}
//第三步： 连接两个分割的链表
lessTail->next=bigGuard->next;
bigTail->next=NULL;
struct ListNode* newhead=lessGuard->next;
free(lessGuard);
free(bigGuard);
lessGuard=NULL;
bigGuard=NULL;
return newhead;
}
};