数据结构——单双链表

顺序表优点：

支持随机访问，内存空间是连续的

顺序表的问题：

①要插删某个元素时效率低，要移动大量元素

②容量固定，扩容成本高

单链表优点：

插删效率高，只需修改相邻节点

动态申请节点，无容量限制

注：单链表不能随机访问，因为不连续。

3.1概念与结构

链表是一种物理存储结构上非连续非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

类比：淡季时车次的车厢会相应减少，旺季时车次的车厢未额外增加几节，只需将货车里的某节车厢去掉或加上不会影响其他车厢，每节车厢都是独立存在的（链表地址不连续）

3.1.1结点

相当于链表里的每节车厢。

组成：要存储的数据+指针（下一个节点的地址）

我们通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点

3.1.2链表的打印

void SLPrintf(SLTNode*phead) {SLTNode *pcur=phead; while(pcur) {printf("%d",pcur->data); pcur=pcur->next; } printf("\n"); }

3.2实现单链表

typedef int SLTDataType; typedef struct SListNode {SLTDataType data; struct SListNode *next; }SLTNode;

创建新节点： void SLTbuyNode(SLTDataType x) {SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode)); if(newnode==NULL) perror("malloc fail") exit(1); } newnode->data=x; newnode->next=NULL; 尾插： void SLTPushBack(SLTNode**pphead,SLTDataType x) { SLTNode* newnode=SLTbuyNode(x); if(*pphead==NULL) { *pphead=newnode;} else { SLTNode ptail=*pphead; while(ptail->next) { ptail=ptail->next;} ptail->next=newnode; } 头插： void SLTPushFront(SLTNode**pphead,SLTDataType x) { assert(pphead); SLTNode* newnode=SLTbuyNode(x); newnode->next=*pphead; *pphead=newnode; } 尾删： void SLTPopBack(SLTNode**pphead) { assert(pphead&&*pphead); if((*pphead)->next==NULL) { free(*pphead); *pphead=NULL; } else { SLTNode* prev=NULL; SLTNode* ptail=*pphead; while(ptail->next) { prev=ptail; ptail=ptail->next; } prev->next=NULL; free(ptail); ptail=NULL; } 头删： void SLTPopFront(SLTNode**pphead) { assert(pphead&&*pphead); SLTNode* next=*pphead->next; free(*pphead); *pphead=next; } 在指定位置之前插入节点： void SLTInsert(SLTNode**pphead,SLTNode* pos,SLTDataType x) { assert(pphead&&pos); if(pos==*pphead) { SLTPushFront(pphead,x); } else { SLTNode* newnode=SLTbuyNode(x); SLTNode* prev=*pphead; while(prev->next=pos) { prev=prev->next; } prev->next=newnode; newnode->next=pos; } 在指定位置之后插入节点： void SLTInsertAfter(SLTNode**pphead,SLTNode* pos,SLTDataType x) { assert(pphead&&pos); SLTNode* newnode=SLTbuyNode(x); newnode->next=pos->next; pos->next=newnode; } 删除pos节点： void SLTErase(SLTNode**pphead,SLTNode* pos) { assert(pphead&&pos); if(pos==*pphead) { SLTPopFront(pphead); else { SLTNode* prev=*pphead; while(prev->next=pos) {prev=prev->next; } prev->next=pos->next; free(pos); pos=NULL; } 删除pos之后的数据： void SLTEraseAfter(SLTNode**pphead,SLTNode* pos) {assert(pphead&&pos); SLTNode* del=pos->next; pos->next=del->next; free(del) del=NULL; } 销毁链表： void SListDestroy(SLTNode**pphead) { SLTNode* pcur=*pphead; while(pcur) {SLTNode* next=pcur->next: free(pcur); pcur=next; } *pphead=NULL; } 查找： void SLTFind(SLTNode*phead,SLTDataType x) {SLTNode* pcur=phead; while(pcur) {if(pcur->data=x) {return pcur; } pcur=pcur->next; } return NULL; }

问：为什么单链表创节点直接sizeof（SLTNode），顺序表还要×newcapacity？
答：单链表每次只创一个节点,只取一个结构体大小，顺序表一次不止加一个元素，newcapacity就是表示一次加几个元素

3.3单链表算法题

移除链表元素

typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head;int val) {ListNode* newHead,*newTail; newHead=newTail=NULL; ListNode* pcur=head; whlile(pcur) { if(pcur->val!=val) { if(newHead==NULL) {newHead=newTail=pcur; } else {newTail->next=pcur; newTail=newTail->next; } } pcur=pcur->next; } if(newTail) newTail->next=NULL; return newHead; }

创建一个新链表，把不是val的放进来

反转链表

typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) {if(head) {return head; } ListNode* n1,*n2,*n3; n1=NULL;n2=head;n3=n2->next; while(n2) {n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; ]

问：为什么n1不直接从head开始？

答：head反转后变成尾节点，它的next为NULL,所以必须在前面设一个n1让head也反转，如果n1=head,虽然2指向1了，但此时1还是指向2，自循环了，所以让所有节点都反转，必须在head前设一个前驱节点

链表的中间节点

typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head） {ListNode*slow=head; ListNode*fast=head; while(fast&&fast->next) {slow=slow->next; fast=fast->next->next; } return slow; }

合并两个有序链表

struct ListNode* mergeTwoList(struct ListNode*list1,struct ListNode*list1) { if(list1) { return list2; } if(list2) { return list1; } ListNode*newHead,*newTail; newHead=newTail=(ListNode*)malloc(sizeof(ListNode)); ListNode*list1=l1; ListNode*list2=l2; while((l1&&l2) { if(l1->val<l2->val) { newTail->next=l1; newTail=newTail->next; l1=l1->next; } else { newTail->next=l2; l2=l2->next; } } if(l2) {newTail->next=l2; } if(l1) {newTail->next=l1;} ListNode* rerHead=newHead->next; free(newHead); newHead=NULL; return retHead; }

问：为什么合并链表newHead...要申请空间？

答：①合并链表头节点先置空后面必须每次考虑链表为空的情况（开始置空只是初始化，之后循环仍需判断空不空），导致代码冗余②直接给一个空间就不用考虑空不空的情况了③起一个哨兵位的作用

链表的回文结构：

bool chkPalindrome(ListNode* A) {ListNode* mid=middleNode(A); ListNode* right=reverseList(mid); ListNode* left=A; while(right) {if(left->val!=right->val) { return false; } left=left->next; right=right->next; } return ture; }

找中间节点断开，左右端点比较是否相等

相交链表：

struct ListNode*getIntersectionNode(struct ListNode *headA,struct ListNode *headB) {ListNode*pa=headA; ListNode*pb=headB; int sizeA=0;sizeB=0; while(pa) {sizeA++; pa=pa->next; } while(pb) {sizeB++; pb=pb->next; } int gap=abs(sizeA-sizeB) ListNode* shortList=headA; ListNode* longList=headB; if(sizeA>sizeB) {longList=headA; shortList=headB; } while(gap--) {longList=longList->next; } while(shortList) {if(longList==shortList) {return longList; } longList=longList->next; shortList=shortList->next; } return NULL; }

算长度差，长链表先走差步，然后两个表同时往后遍历

判断链表是否有环：

typedef struct ListNode ListNode; bool hasCycle(struct ListNode* head) { ListNode*slow; ListNode*fast; while(fast&&fast->next) {slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } } return false; }

快慢指针在环里一定会相遇

返回入环的第一个节点

typedef struct ListNode ListNode; struct ListNode* detectCycle(struct ListNode* head) { ListNode*slow; ListNode*fast; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { ListNode* pcur=head; while(pcur!=slow) { pcur=[cur->next; slow=slow->next: } return pcur; } } return NULL; }

相遇点和头节点到入环第一个节点距离相等

3.4双向链表

带头链表里的头节点实际为哨兵位，不存储任何有效元素

3.4.1实现双向链表

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

初始化： LTNode* LTBuyNode(LTDataType x) { LTNode* newnode=(LTNode*)malloc(sizeof(LTNdode)); if(newnode==NULL) {perror("malloc fail"); exit(1); } newnode->data=x; newnode->next=newnode->prev=newnode; return newnode; } void LTInit(LTNode**pphead) {assert(ppheadd); *pphead=LTBuyNode(-1) }

尾插： void LTPushBack(LTNode* phead,LTDataTyoe x) {assert(phead); LTNode* newnode=LTBuyNode(x); newnode->prev=phead->prev; newnide->next=phead; } 头插: void LTPushFront(LTNode* phead,LTDataTyoe x) {assert(phead); LTNode* newnode=LTBuyNode(x); newnode->next=phead->next; newnode->prev=phead; } 尾删： void LTPopBack(LTNode* phead) {assert(phead); LTNode* del=phead->next; del->prev->next=phead; phead->prev=del->prev; free(del); del=NULL; } 头删： void LTPopFront(LTNode* phead) { assert(phead); LTNode* del=phead->next; del->next->prev=phead; phead->next=del->next; free(del); del=NULL; } 在pos位置之后插入数据： void LTInsert(LTNode* phead,LTDataTyoe x) {assert(pos); LTNode* newnode=LTBuyNode(x); newnode->next=pos->next; newnode->prev->pos; } 删除pos位置的节点： void LTErase(LTNode*pos) {assert(pos); pos->next->prev=pos->prev; pos-prev->next=pos->next; free(pos); pos=NULL; } 销毁： void LTDestroy(LTNode* phead) {LTNode* pcur=phead->next; while(pcur) {LTNode* next=pcur->next; free(pcur); pcur=NULL; } free(phead); phead=NULL; }

尾/头插：从新节点看前后连接啥

尾/头删：用del保存要删的节点，注意这里的头删删的是phead->next（双向链表的头节点不可被删除），通过del看怎样连是phead，然后再看phead和del的关系

当单链表为空时，指向第一个节点的指针为空；当双向链表中=为空时，链表中只有一个头节点

问：为什么双向链表不传二级指针？

答：带头双向链表不修改头节点，只改节点指向的内容（房子里的家具），一级即可，头节点是指针（房子本身），单链表里要改必须传二级，