考研408 王道 数据结构 算法题整理(二)链表
考研408 王道 数据结构 算法题整理(二)链表
·
2.1.1 链表的定义和结构
单链表(data是该节点的权值,一般可以定义成int;next是指向下一个节点的指针,保存的是下一个节点的位置):
typedef struct LNode{
Elemtype data; //该节点的权值
struct LNode *next; //next指向下一个节点
}LNode;
双链表(不需要特别记忆,只是比单链表多一个prior指针而已):
typedef struct LNode{
Elemtype data; //该节点的权值
struct LNode *prior,*next; //prior指向上一个节点
}LNode;
2.1.2 总结数组做题流程——暴力——优化方向
- 暴力解法:枚举法,直接处理;将链表用数组保存,再处理
- 设置多指针后移
前后指针——前后距离是一样的(查找倒数第k个)
快慢指针——如果有环,快指针早晚追上慢指针
头插法——逆置
2.1.3 插入操作(头插、尾插)代码
头插法建立单链表
LinkList List_HeadInsert(LinkList &L, int e){
LNode *s,*p;
s=(LNode *)malloc(sizeof(LNode));
s->data=e;
p=L; //p指向链表头结点
s->next=p->next;
p->next=s;
}
尾插法建立单链表
LinkList List_TailInsert(LinkList &L, int e){
LNode *s,*r;
r=L; //r为表尾指针
s=(LNode *)malloc(sizeof(LNode));
s->data=e;
r->next=s;
r=s;
r->next=null;
}
2.1.4 删除操作代码
void LNodeDelete(LinkList &L,int &e){
pre=GetElem(L,i-1); //找到删除位置的前驱节点
p=pre->next;
e=p->data;
pre->next=p->next;
free(p);
}
2.1.5 逆置操作代码
void ReverseLinkList(LinkList &L){
LNode *p,*r;
p=L->next;
L->next=NULL;
while(p!=NULL){
r=p->next;
p->next=L->next;
L->next=p;
p=r;
}
}
2.3.1 P40.1 删除值为x的结点
void delX(LinkList &L,int x){
LNode *pre=L;
while(pre->next!=NULL){
LNode *p=pre->next;
if(p->data==x){
pre->next=p->next;
free(p);
}
pre=pre->next;
}
}
2.3.2 P40.5 单链表就地逆置
void ReverseLinkList(LinkList &L){
LNode *p,*r;
p=L->next;
L->next=NULL;
while(p!=NULL){
r=p->next;
p->next=L->next;
L->next=p;
p=r;
}
}
2.3.3 P40.6 将链表排序
void SortLinkList(LinkList &L){ //直接插入排序
LNode *p=L->next,*pre;
LNode *r=p->next;
p->next=NULL;
p=r;
while(p!=NULL){
r=p->next;
pre=L;
while(pre->next!=NULL && pre->next->data < p->data){
pre=pre->next;
}
p->next=pre->next;
pre->next=p;
p=r;
}
}
2.3.4 P40.11 拆分链表
void DivideLinkList(LinkList &C,LinkList &B){
LNode *hc=C; LNode *pc=hc->next; LNode *pcb=pc->next;
B=(LinkList)malloc(sizeof(LNode));
B->next=NULL;
LNode *hb=B;
while(pc->next!=NULL){
if(pc->next->next==NULL){
pc->next=NULL;
pcb->next=hb->next;
hb->next=pcb;
}
else{
pc->next=pcb->next;
pc=pc->next;
pcb->next=hb->next;
hb->next=pcb;
pcb=pc->next;
}
}
}
2.3.5 P40.12 删除链表中的重复元素
void DelDupliNum(LinkList &L){
LNode *pre=L;
while(pre->next!=NULL){
LNode *p=pre->next;
if(pre->data==p->data){
pre->next=p->next;
free(p);
}
else{
pre=pre->next;
}
}
}
2.3.6 将两个递增链表合并成一个递增链表
LinkList MergeLinkList(LinkList A,LinkList B){
LinkList C=(LinkList)malloc(sizeof(LNode));
C->next=NULL;
LNode *r=C;
LNode *pa=A->next;
LNode *pb=B->next;
while(pa!=NULL&&pb!=NULL){
if(pa->data<=pb->data){
r->next=pa;
r=pa;
pa=pa->next;
}
else{
r->next=pb;
r=pb;
pb=pb->next;
}
}
while(pa!=NULL){
r->next=pa;
r=pa;
pa=pa->next;
}
while(pb!=NULL){
r->next=pb;
r=pb;
pb=pb->next;
}
return C;
}
2.3.7 P40.13 将两个递增链表合并成一个递减链表
void MergeLinkList(LinkList &A,LinkList &B){
LNode *head=A;
LNode *pa=A->next;
LNode *pb=B->next;
while(pa!=NULL&&pb!=NULL){
if(pa->data>=pb->data){
head->next=pa;
head=pa;
pa=pa->next;
}
else{
head->next=pb;
head=pb;
pb=pb->next;
}
}
while(pa!=NULL){
head->next=pa;
head=pa;
pa=pa->next;
}
while(pb!=NULL){
head->next=pb;
head=pb;
pb=pb->next;
}
}
2.3.7 P40.13 将两个递增链表合并成一个递减链表
void MergeLinkList_TwoUp_To_Down(LinkList &A,LinkList &B){
LNode *head=A,*r;
LNode *pa=A->next;
LNode *pb=B->next;
A->next=NULL;
while(pa!=NULL&&pb!=NULL){
if(pa->data<=pb->data){
r=pa->next;
pa->next=head->next;
head->next=pa;
pa=r;
}
else{
r=pb->next;
pb->next=head->next;
head->next=pb;
pb=r;
}
}
if(pa) pb=pa;
while(pb!=NULL){
r=pb->next;
pb->next=head->next;
head->next=pb;
pb=r;
}
}
2.3.8 P40.17 判断一个循环双链表是否对称
int Symmetry(DLinkList L){
DNode *p=L->next, *q=L->prior;
while(p!=q&&q->next!=p){
if(q->data==p->data){
q=q->next;
p=p->next;
}
else return 0;
}
return 1;
}
2.3.9 P40.19 依次输出链表中结点值最小的元素
void delALL(LinkList &L){
LNode *p,*pre,*minp,*minpre;
while(L->next!=L){
p=L->next; pre=L;
minp=p; minpre=pre;
while(p!=L){
if(p->data < minp->data){
minp=p;
minpre=pre;
}
pre=p;
p=p->next;
}
cout<<minp->data;
minpre->next=minp->next;
free(minp);
}
}
2.3.10 P40.21 判断链表中是否存在环(快慢指针的应用)
bool *ListHasLoop(LNode *head){
LNode *fast=head, *slow=head;
while(fast!=NULL&&fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
if(fast==slow) return true;
}
if(slow==NULL||fast->next==NULL) return false;
//寻找相遇点
// LNode *p1=head, *p2=slow;
// while(p1!=p2){
// p1=p1->next;
// p2=p2->next;
// } //p1即为相遇点
}
更多推荐
所有评论(0)