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; } };
