1.单链表的结构体定义

1
2
3
4
typedef struct LNode{
    int data; //根据结点存储元素的类型选择数据域的数据类型 
    struct LNode *next;//指针域用于记录链表中下一个结点的位置
}LNode,*LinkList;

单链表的初始化

  • 带头结点
1
2
3
4
void InitList(LinkList &L){//函数需要通过形参 L 改变实参，故需引用 
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    L->next=NULL;//头结点指针域置空
}
  • 不带头结点
1
2
3
void InitList(LinkList &L){//函数需要通过形参 L 改变实参，故需引用 
    L=NULL;//头指针置空
}

2.单链表的遍历

题目：遍历输出带头结点的单链表L中各结点数据域的值

思路：定义遍历指针p,初始化为第一个数据节点的位置，也就是头结点指针域指向的地方，遍历输出

1
2
3
4
5
6
7
8
9
void ListVisit(LinkList L){
    if(L->next==NULL)//若链表为空表，则直接返回 
        return;
    LNode *p=L->next;//定义遍历指针 p 并初始化在第一个数据结点位置 
    while(p!=NULL){//循环遍历此链表
        printf("%d ",p->data);//打印 p 指向结点数据域的值 
        p=p->next;//遍历指针后移，继续遍历
    }
}时间复杂度和空间复杂度分别为：O(n)和O(1)

3.计算单链表的长度

题目：计算带头结点的单链表L中数据结点的个数

思路：遍历＋计数

1
2
3
4
5
6
7
8
9
10
11
int Length(LinkList L){
    if(L->next==NULL)//若链表为空表，则长度为 0 
        return;
    LNode *p=L->next;//定义遍历指针 p 并初始化在第一个数据结点位置 
    int length=0;//定义计数变量 length
    while(p!=NULL){ //遍历此链表
        length++;//p 指向结点不为空，进行计数 
        p=p->next;//遍历指针后移，继续遍历
    }
    return length; //返回链表 L 中数据结点的个数
}时间复杂度和空间复杂度分别为：O(n)和O(1)

4.单链表的按序查找

题目：请设计一个算法，查找一个带头结点的单链表L中第i个数据结点的位置，若存在，则返回指向该结点的指针，若不存在，则返回NULL

思路：遍历+计数

1
2
3
4
5
6
7
8
9
10
11
12
13
LNode *Search_i(LinkList L,int i){
    if(L->next==NULL||i<1) //若链表为空或 i 的输入不合法，则直接返回 NULL 
        return NULL;
    LNode *p=L->next;//定义遍历指针 p
    int k=1;//定义变量 k，用于记录 p 指向结点的位序 
    while(p!=NULL){//遍历该链表
        if(k==i)//若 p 指向结点为查找结点，则返回指针 p 
            return p;
        p=p->next;//遍历指针后移，继续遍历 
        k++;//更新变量 k
    }
    return NULL;//若遍历结束仍没有找到查找结点，则返回 NULL
}时间复杂度和空间复杂度分别为：O(n)和O(1)

5.单链表的按值查找

题目：请设计一个算法，查找一个带头结点的单链表L中第1个值为e的结点位置，若存在，则返回指向该结点的指针，若不存在，则返回NULL

思路：遍历

1
2
3
4
5
6
7
8
9
10
11
LNode *Search_e(LinkList L,int e){
    if(L->next==NULL)//若链表为空表，则直接返回 NULL 
        return NULL;
    LNode *p=L->next;//定义遍历指针 p 
    while(p!=NULL){//遍历该链表
        if(p->data==e)//若 p 指向结点为查找结点，则返回指针 p 
            return p;
        p=p->next; //遍历指针后移，继续遍历
    }
    return NULL; //若遍历结束仍没有找到查找结点，则返回 NULL
}时间复杂度和空间复杂度分别为：O(n)和O(1)

6.有序单链表插入一个新结点后依然有序

题目：在一个带头结点的非递减有序单链表中插入一个值为x的新结点，使得插入新结点后链表依然非递减有序

思路：pre指向头结点，p指向第一个数据元素，若空表则p初始化为NULL直接插入，遍历找到第一个比x大的元素，将x插入该元素之前

1
2
3
4
5
6
7
8
9
10
11
12
13
void ListInsert(LinkList L,int x){
    LNode *pre=L,p=L->next;//定义遍历指针 p 和前驱指针 pre 
    while(p!=NULL){//遍历该链表
        if(p->data>x)//若 p 指向结点数据域大于 x，则找到插入位置 
            break;//找到插入位置，跳出循环
        pre=p;//没有找到插入位置，继续遍历 
        p=p->next;
    }
    LNode *s=(LinkList)malloc(sizeof(LNode));//创建新结点 
    s->data=x;//为新结点数据域赋值
    pre->next=s; //将新结点插入到链表中 
    s->next=p;
}时间复杂度和空间复杂度分别为：O(n)和O(1)

7.头插法建立单链表

题目：采用头插法在头指针工处建立一个带头结点的单链表，输入-1表示结束，头插结束后返回建立的
单链表。

思路：将新节点插在头结点之后，初始化时要将头结点置空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList HeadInsert(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next=NULL;//初始化头结点
    LNode *s;//定义辅助指针 s 
    int x;//定义辅助变量 x
    scanf("%d",&x);//输入新结点数据域中的值
    while(x!=-1){
        s=(LinkList)malloc(sizeof(LNode));//输入-1 表示所有新结点数据域的值输入完毕 
        s->data=x; //为新结点数据域赋值
        s->next=L->next;//头插法核心代码 
        L->next=s;//头插法核心代码
        scanf("%d",&x);//继续输入下一结点数据域的值 
    }
    return L; //返回新链表头指针 L
}时间复杂度和空间复杂度分别为：O(n)和O(1)

8.尾插法建立单链表

题目：采用尾插法在头指针L处建立一个带头结点的单链表，输入-1表示结束，尾插结束后返回建立的单链表

思路：将新节点插在尾结点之后，插入结束后将尾指针置空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkList TailInsert(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    LNode *r=L;//尾插法核心代码（定义尾指针 r）
    LNode *s; //定义辅助指针 s
    int x;//定义辅助变量 x
    scanf("%d",&x);//输入新结点数据域的值
    while(x!=-1){ //输入-1 表示所有新结点数据域的值输入完毕 
        s=(LinkList)malloc(sizeof(LNode));//创建新结点
        s->data=x;//为新结点数据域赋值 
        r->next=s; //尾插法核心代码
        r=s;//尾插法核心代码（更新尾指针位置） 
        scanf("%d",&x);//继续输入下一结点数据域的值
    }
    r->next=NULL;//尾插法核心代码（尾插结束后尾结点指针域置空） 
    return L;//返回新链表头指针
}时间复杂度和空间复杂度分别为：O(n)和O(1)

9.单链表的逆置

题目：试编写算法将一个带头结点的单链表L就地逆置，所谓“就地"是指空间复杂度为O(1)

思路：头插法将单链表逆置（放断链指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
void Reverse(LinkList L){
    if(L->next==NULL)
        return;
    //r为防断链指针，记录所处理结点的下一结点
    LNode *p=L->next,*r;//定义遍历指针 p，r 为头插操作的防断链指针 
    L->next=NULL;//头结点指针域置空
    while(p!=NULL){//遍历链表，将遍历结点重新进行头插
        r=p->next;//防断链指针记录下一个遍历结点位置，防止头插断链 
        p->next=L->next;//头插法核心代码
        L->next=p; //头插法核心代码
        p=r;//p 指针更新到下一遍历结点位置
    }
}时间复杂度和空间复杂度分别为：O(n)和O(1)

10.一个单链表按位序分解为两个单链表（尾插+尾插）

题目：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中位序为奇数的结点，B表中含有原表中位序为偶数的结点，且保持结点间相对顺序不变，最后返回B表

思路：尾插法（两个元素为一组进行尾插）（尾结点置空）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LinkList Create_A_B(LinkList A){
    if(A->next==NULL)
        return NULL:
    LinkList B=(LinkList)malloc(sizeof(LNode));//创建 B 表头结点
    LNode *p=A->next,*ra=A,*rb=B;//定义遍历指针 p 和 A 表 B 表的尾指针 
    while(p!=NUll){//遍历原 A 表
        ra->next=p;//将遍历结点尾插到 A 表 
        ra=p; //更新 A 表尾指针
        p=p->next; //更新遍历指针，继续遍历
        if(p!=NULL){//防止最后一次循环因为只有一个结点而报错 
            rb->next=p;//将遍历结点尾插到 B 表
            rb=p;//更新 B 表尾指针
            p=p->next; //更新遍历指针，继续遍历
        }
    }
    ra->next=NULL; //A 表尾结点指针域置空
    rb->next=NULL;//B 表尾结点指针域置空
    return B;//分解完成后返回 B 表头指针
}时间复杂度和空间复杂度分别为：O(n)和O(1)

11.一个单链表按位序分解为两个单链表（尾插+头插）

题目：编写算法将一个带头结点的单链表A={a1,b1,a2,b2,…,an,bn}分解为两个带头结点的单链表A和B,使得A={a1,a2,…,an}，B={bn,…,b2,b1}，原A表中结点个数不一定为偶数

思路：A表尾插，B表头插，尾插注意尾结点置空，头插注意放断链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LinkList Create_A_B(LinkList A){
    if(A->next==NULL)
        return NULL:
    LinkList B=(LinkList)malloc(sizeof(LNode));//创建 B 表头结点 
    B->next=NULL; //头插法需要先对头结点指针域置空
    LNode *p=A->next,*r=A,*q;//定义遍历指针，A 表尾指针和 B 表防断链指针 
    while(p!=NULL){//遍历原 A 表
        r->next=p; //将遍历结点尾插到 A 表 
        r=p;//更新 A 表尾指针
        p=p->next;//更新遍历指针，继续遍历
        if(p!=NULL){//防止最后一次循环因为只有一个结点而报错 
            q=p->next;//防断链指针记录下一个遍历结点位置
            p->next=B->next;//头插法核心代码//头插法核心代码
            B->next=p;//头插法核心代码
            p=q; //更新遍历指针，继续遍历
        }
    }
    r->next=NULL; //A 表尾结点指针域置空 
    return B;//返回 B 表头指针
}时间复杂度和空间复杂度分别为：O(n)和O(1)

12.一个单链表按结点值的奇偶分解为两个单链表（尾插+尾插）

题目：将一个带头结点的单链表L分解为两个带头结点的单链表A和B，使得A表中含有原表中数据域为奇数的结点，而B表中含有原表中数据域为偶数的结点，且保持相对顺序不变，最后删除单链表L的头结点

思路：尾插法（尾结点置空）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LinkList Create_A_B(LinkList L,LinkList &A,LinkList &B){
    if(A->next==NULL)//若链表为空表，则直接结束函数 
        return NULL:
    LinkList A=(LinkList)malloc(sizeof(LNode));//创建 A 表头结点 
    LinkList B=(LinkList)malloc(sizeof(LNode)); //创建 B 表头结点
    LNode *p=L->next,*ra=A,*rb=B;//定义遍历指针 p 和 A 表 B 表的尾指针
    while(p!=NULL){ //遍历单链表 L
        if(p->data%2==1){//若遍历结点数据域为奇数，则尾插 A 表
            ra->next=p;//将遍历结点尾插到 A 表
            ra=p; //更新 A 表尾指针
            p=p->next;//更新遍历指针，继续遍历
        }
        else{
            rb->next=p;//将遍历结点尾插到 B 表
            rb=p;//更新 B 表尾指针 
            p=p->next;//更新遍历指针，继续遍历
        }
    }
    A->next=NULL;//A 表尾结点指针域置空 
    B->next=NULL;//B 表尾结点指针域置空 
    free(L);//删除链表 L 的头结点
}时间复杂度和空间复杂度分别为：O(n)和O(1)

13.删除链表中的最小值结点

题目：有一个带头结点单链表L,L中各个结点的值都不相同，请设计一个算法，删除链表L中的最小值结点

思路：遍历找到最小值结点，记录该节点以及其前驱结点，删除最小值结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Del_Min(LinkList L){
    if(L->next==NULL)//若链表为空表，则直接结束函数 
        return;
    LNode *minpre=L,*minp=L->next; //记录已遍历结点中最小值结点及其前驱 
    LNode *pre=L->next,*p=pre->next;//定义遍历指针 p 及其前驱指针 pre 
    while(p!=NULL){//遍历单链表
        if(p->data<minp->data){ //遍历结点的值是否小于之前记录的最小值结点 
            minp=p;//若遍历结点值更小，则更新最小值结点位置
            minpre=pre; //更新最小值结点前驱结点位置 
        }
        pre=p;//继续遍历 
        p=pre->next;
    }
    minpre->next=minp->next;//遍历结束，将最小值结点从链表中删除 
    free(minp); //释放最小值结点空间
}时间复杂度和空间复杂度分别为：O(n)和O(1)

14.删除单链表中删除所有值为x的结点

题目：请设计一个算法，在带头结点的单链表L中删除所有值为x的结点，并释放其空间

思路：遍历删除所有等于x的结点（需用到其前驱结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Del_x(LinkList L,int x){
    if(L->next==NULL)//若链表为空表，则直接结束函数 
        return;
    LNode *pre=L,*p=L->next;//定义遍历指针 p 及其前驱指针 pre 
    while(p!=NULL){//遍历该链表
        if(p->data==x){//若遍历结点数据域等于 x，则删除该遍历结点 
            pre->next=p->next; //删除数据域为 x 的结点
            free(p);//释放被删结点的空间
            p=pre->next; //遍历指针更新到下一遍历结点位置
        }
        else{//若遍历结点数据域不等于 x，则遍历指针后移，继续遍历 
            pre=p;
            p=pre->next;
        }
    }
}时间复杂度和空间复杂度分别为：O(n)和O(1)

15.删除单链表中所有数据域的值介于给定的两个值之间的结点

题目：请设计一个算法，在带头结点的单链表L中删除所有数据域的值介于给定的两个值之间的结点并释放其空间

思路：遍历删除所有大于s小于t的结点（需用到其前驱结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Del_s_t(LinkList L,int s,int t){
    if(L->next==NULL||s>=t)//若链表为空或给定值不合法，则结束函数
        return;
    LNode *pre=L,*p=L->next;//定义遍历指针 p 及其前驱指针 pre
     while(p!=NULL){
         if(p->data>s&&p->data<t){ //判断遍历结点值是否在 min 与 max 间 
             pre->next=p->next;//遍历结点值在 min 与 max 之间，则删除该结点
             free(p); //释放被删结点空间 //释放被删结点空间
             p=pre->next;//更新遍历指针位置
         }
         else{ //若遍历结点值不在 min 与 max 之间，则遍历指针后移，继续遍历 
             pre=p;
             p=pre->next;
         }
     }
}时间复杂度和空间复杂度分别为：O(n)和O(1)

16.删除非递减有序链表中所有值重复的结点

题目：请设计一个算法，在带头结点的非递减有序单链表L中删除所有值重复的结点，使值重复的结点只保留一个

思路：遍历删除所有跟其前驱结点数据域相等的的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Del_Same(LinkList L){
    if(L->next==NULL)//若链表为空表,则直接结束函数 
        return;
    LNode *pre=L-next,*p=pre->next;//定义遍历指针及其前驱指针并初始化 
     while(p!=NULL){ //遍历该链表
         if(p->data>s==pre->data){//若遍历结点与前驱结点值相同，则证明重复 
             pre->next=p->next;//若重复，则删除遍历指针指向的重复结点 
             free(p); //释放被删结点所占空间
             p=pre->next;//更新遍历指针位置
         }
         else{//若遍历结点与前驱结点值不重复，则遍历指针后移，继续遍历 
             pre=p;
             p=pre->next;
         }
     }
}时间复杂度和空间复杂度分别为：O(n)和O(1)

17.删除无序链表中所有值重复的结点

题目：请设计一个算法，在带头结点的无序单链表L中删除所有值重复的结点，使值重复的结点只保留一个

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Del_Same(LinkList L){
    if(L->next==NULL)//若链表为空表,则直接结束函数 
        return;
    LNode *r=L->next;//定义遍历指针 r，记录当前比较结点
    LNode *pre,*p;//定义遍历指针 pre 和 p，遍历当前比较结点的所有后续结点 
    while(r!=NULL){ //遍历该链表
        pre=r; //每一次进入循环都需要重新初始化 pre 指针和 p 指针 
        p=pre->next;
        while(p!=NULL){ //遍历 r 指向结点的所有后续结点
            if(p->data==r->data){ //若遍历结点与 r 指向结点值相同，则证明重复 
                pre->next=p->next;//若重复，则删除遍历指针 p 指向的重复结点
                free(p);//释放被删结点所占空间
                p=pre->next; //更新遍历指针位置
            }
            else{//若 p 指向结点与 r 指向结点值不重复，则指针后移，继续遍历 
                pre=p;
                p=pre->next;
            }
        }
        r=r->next; //r 指向结点比较结束后，继续后移，比较下一个结点
    }
}时间复杂度和空间复杂度分别为：O(n^2)和O(1)

18.两个递增有序单链表求交集生成新链表

题目：设A和B是带头结点的递增有序单链表，请设计一个算法，求单链表A与B的交集，并生成个新的单链表C，要求不破坏A、B的结点

思路：同时遍历两表，找出遍历元素中的较大值，让较小的元素后移，与较大值看齐，便可找到两链表中值相同结点，插入C表，尾插法需要尾指针以及最后尾结点置空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
LinkList Union(LinkList A,LinkList B){
    if(A->next==NULL||B->next==NULL) //A 和 B 有一个是空表，直接结束函数
        return NULL;
    LNOde *p=A->next,*q=B->next,*r; //定义遍历指针 p 和 q，C 表尾指针 r 
    LNode *s;//定义辅助指针 s，创建新结点时使用 
    LinkList C=(LinkList)malloc(sizeof(LNode));//创建 C 表头结点
    r=C;
    while(p!=NULL&&q!=NULL){//若两个表有任意一个处理完毕，则停止循环
        if(p->data<q->data)//若 A 表中遍历结点值更小，则 p 指针后移 
            p=p->next;
        else if(p->data>q->data) //若 B 表中遍历结点值更小，则 q 指针后移 
            q=q->next;
        else{//找到值相同的交集结点，则创建新结点尾插到 C 表 
            s=(LinkList)malloc(sizeof(LNode));//创建一个新结点//创建一个新结点
            s->data=p->data;//为新结点数据域赋值 
            r->next=s;//将新结点尾插到 C 表中
            r=s;//更新尾指针位置
            p=p->next;//两指针继续遍历寻找交集结点 
            q=q->next;
        }
    }
    r->next=NULL; //尾插结束后，尾结点指针域置空 
    return C; //返回 C 表的头指针
}时间复杂度和空间复杂度分别为：O(m+n)和O(1)

19.两个递增有序单链表求交集存放到原链表

题目：设A和B是两个带头结点的递增有序单链表，请设计一个算法，求单链表A与B的交集，并存放于A链表中，其它结点均释放其空间

思路：同时遍历两表，找出遍历元素中的较大值，让较小的元素后移，与较大值看齐，便可找到两链表中值相同结点，插入A表，一个链表遍历结束后将剩余链表内存释放，尾插法需要尾指针以及最后尾结点置空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
LinkList Union(LinkList &A,LinkList &B){
    if(A->next==NULL||B->next==NULL)//A 和 B 有一个是空表，直接结束函数
        return NULL;
    LNOde *p=A->next,*q=B->next,*r=A;//定义遍历指针 p 和 q，新 A 表尾指针 r 
    LNode *s; //定义防断链指针 s
    while(p!=NULL&&q!=NULL){//若两个表有任意一个处理完毕，则停止循环 
        if(p->data<q->data){ //若 p 指向结点值较小，则删除此结点并后移 p
            s=p->next; //s 指针记录原 A 表下一个遍历结点位置，防止断链 
            free(p); //删除 p 指向的值较小结点
            p=s; //p 更新到原 A 表中下一个遍历结点位置
        }
        else(p->data>q->data){//若 q 指向结点值更小，则删除此结点
            s=q->next; 
            free(q);
            q=s;
        }
        else{ //找到两个链表的交集结点，将其中一个尾插到新 A 表 
            r->next=p;//将 p 指向的交集结点尾插到新 A 表中
            r=p;//更新尾指针位置
            p=p->next;//p 指针继续遍历
            s=q->next;//s 指针记录 B 表下一个遍历结点位置，防止断链
            free(q);//删除 q 指向结点
            q=s;//q 更新到 B 表中下一个遍历结点位置
        }
    }
    while(p!=NULL){//若循环结束后原 A 表有剩余结点，则全部删除释放空间 
        s=p->next;//s 指针记录原 A 表下一个遍历结点位置，防止断链
        free(p);//删除 p 指向的值较小结点
        p=s;//p 更新到原 A 表中下一个遍历结点位置
    }
    while(q!=NULL){ //若循环结束后 B 表有剩余结点，则全部删除释放空间 
        s=q->next;
		free(q); 
        q=s;
}
    r->next=NULL;//尾插结束后尾结点指针域需置空
    free(B);//删除 B 表头结点
    return A;//返回 A 表头指针
}时间复杂度和空间复杂度分别为：O(m+n)和O(1)

20.两个递增有序单链表归并为一个非递减有序单链表

思路：（尾插法）同时遍历两表，找出遍历元素中的较小值，插入A表，一个链表遍历结束后将剩余链表插入A表，尾插法需要尾指针以及最后尾结点置空

题目：设A和B是两个带头结点的递增有序单链表，请设计一个算法，将A和B两个单链表归并为一个带头结点的非递减有序单链表，要求利用原来两个单链表的结点组成归并后的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
LinkList Merge(LinkList A,LinkList B){
	if(A->next==NULL&&B->next==NULL) //链表 A，B 都为空，直接结束函数
        return NULL;
    LNode *p=A->next,*q=B->next,*r=A;//定义遍历指针 p，q 和新 A 表尾指针 r 
    while(p!=NULL&&q!=NULL){//若两个表有任意一个处理完毕，则停止循环
        if(p->data<=q->data){//将两个遍历结点中值较小的结点尾插到新 A 表 
            r->next=p;//尾插 p 指向结点
            r=p;//更新尾指针位置
            p=p->next;//遍历指针继续遍历
        }
        else{
            r->next=q;//尾插 q 指向结点
            r=q;//更新尾指针位置
            q=q->next;//遍历指针继续遍历
        }
    }
    while(p!=NULL){ //若原 A 表有剩余结点，则将剩余结点挨个尾插到新 A 表 
        r->next=p; //尾插 p 指向结点
        r=p; //更新尾指针位置
        p=p->next;//遍历指针继续遍历
    }
    while(q!=NULL){ //若原 B 表有剩余结点，则将剩余结点挨个尾插到新 A 表 
        r->next=q; //尾插 q 指向结点
        r=q; //更新尾指针位置
        q=q->next;//遍历指针继续遍历
    }
    r->next=NULL;//尾插结束后，尾结点指针域置空 
    free(B); //释放 B 表头结点空间
    return A;//返回归并后新 A 表的头指针
}时间复杂度和空间复杂度分别为：O(m+n)和O(1)

21.两个递增有序单链表归并为一个非递增有序单链表

题目：设A和B是两个带头结点的递增有序单链表，请设计一个算法，将A和B两个单链表归并为一个带头结点的非递增有序单链表，要求利用原来两个单链表的结点组成归并后的单链表

思路：（头插法）同时遍历两表，找出遍历元素中的较小值，插入A表，一个链表遍历结束后将剩余链表插入A表，头插法注意防断链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
LinkList Merge(LinkList A,LinkList B){
	if(A->next==NULL&&B->next==NULL)//链表 A，B 都为空，直接结束函数
        return NULL;
    LNode *p=A->next,*q=B->next,*r;//定义遍历指针 p，q 和防断链指针 r
    A->next=NULL;//新 A 表头结点指针域置空，保证头插后尾结点指针域为空 
    while(p!=NULL&&q!=NULL){ //若两个表有任意一个处理完毕，则停止循环
        if(p->data<=q->data){ //将两个遍历结点中值较小的结点头插到新 A 表 
            r=p->next;//指针 r 记录下一个遍历结点位置
            p->next=A->next;//头插指针 p 指向结点 
            A->next=p; //头插指针 p 指向结点
            p=r; //遍历指针继续遍历 
        }
        else{
            r=q=->next; //指针 r 记录下一个遍历结点位置 
            q->next=A->next;//头插指针 q 指向结点
            A->next=q;//头插指针 q 指向结点 
            q=r; //遍历指针继续遍历
        }
    }
    while(p!=NULL){//若原 A 表有剩余结点，则将剩余结点挨个头插到新 A 表 
        r=p->next;//指针 r 记录下一个遍历结点位置
        p->next=A->next;//头插指针 p 指向结点
        A->next=p;//头插指针 p 指向结点
        p=r;//遍历指针继续遍历
    }
    while(q!=NULL){ //若 B 表有剩余结点，则将剩余结点挨个头插到新 A 表 
        r=q->next; //指针 r 记录下一个遍历结点位置
		q->next=A->next; //头插指针 q 指向结点 
        A->next=q; //头插指针 q 指向结点
		q=r; //遍历指针继续遍历 
    }
    frer(B);//释放 B 表头结点空间
    return A;//返回归并后新 A 表的头指针
}时间复杂度和空间复杂度分别为：O(m+n)和O(1)

22.两个递增有序单链表求差集

思路：同时遍历两表，A表较小则插入，B表较小则释放内存，相等则同时释放，一个链表结束遍历后，A表剩余则插入，B表剩余则释放，尾插法需要尾指针以及最后尾结点置空

题目：设A和B是两个带头结点的递增有序单链表，请设计一个算法，求单链表A与B的差集，并返回差集链表。链表A与B的差集定义为:在链表A中存在但不在链表B中存在的所有结点的集合。要求利用原来两个单链表的结点组成差集链表，其它结点均释放其空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
LinkList Diff(LinkList A,LinkList B){//链表 A 和 B 有一个为空，结束函数 
    if(A->next==NULL||B->next==NULL)
        return NULL;
    LNode *p=A->next,*q=B->next,*r=A;//定义遍历指针 p，q 和尾指针 r 
    LNode *s;//定义防断链指针 s
    while(p!=NULL&&q!=NULL){//若两个表有任意一个处理完毕，则停止循环
        if(p->data<q->data){//若 p 指向结点值更小，则将此结点尾插到新 A 表
            r->next=p;//尾插 p 指向遍历结点
            r=p; //更新尾指针位置
            p=p->next; //遍历指针继续遍历
        }
        else if(p->data>q->data){//若 q 指向结点值更小，则删除此结点 
            s=q->next;//防断链指针 s 记录下一个遍历结点位置 
            free(q); //删除 q 指向遍历结
            q=s;//遍历指针继续遍历 
        }
        else{
            s=p->next;//防断链指针 s 记录下一个遍历结点位置 
            free(p); //删除 p 指向遍历结点
            p=s;//遍历指针继续遍历
            s=q->next;//防断链指针 s 记录下一个遍历结点位置 
            free(q);//删除 q 指向遍历结点
            q=s;//遍历指针继续遍历
        }
    }
    while(p!=NULL){//若原 A 表有剩余结点，则将剩余结点挨个尾插到新 A 表 
        r->next=p;//尾插 p 指向遍历结点
        r=p;//更新尾指针位置
        p=p->next; //遍历指针继续遍历 
    }
    while(q!=NULL){//若 B 表有剩余结点，则将剩余结点挨个删除
        s=q->next; //防断链指针 u 记录下一个遍历结点位置
        free(q);//删除 q 指向遍历结点
        q=s;//遍历指针继续遍历
    }
    r->next=NULL;//尾插结束后，尾结点指针域置空 
    free(B);//释放 B 表头结点空间
    return A; //返回新 A 表的头指针，即差集链表的头指针
}时间复杂度和空间复杂度分别为：O(m+n)和O(1)

23.判断序列B是否为序列A的连续子序列

题目：两个整数序列 A={a1,a2,a3,…,am}和 B={b1,b2,b3,…,bn}已经存入两个带头 结点的单链表中。请设计一个算法，判断序列B是否是序列A的连续子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool Pattern(LinkList A,LinkList B){
    LNode *p=A->next,*q=B->next;//定义遍历指针 p 和 q
    LNode *pre=A->next;//指针 pre 负责记录链表 A 中此次比较的起始结点位置 
    while(p!=NULL&&q!=NULL){ //遍历链表 A 与链表 B，进行比较
        if(p->data==q->data){//若两遍历结点数据域相同，则需继续遍历 
            p=p->next;
            q=q->next;
        }
        else{//若两遍历结点数据域不同，则证明此次比较失败
            pre=pre->next; //指针 pre 更新到链表 A 中下一次比较的起始位置 
            p=pre; //指针 p 回到链表 A 中下一次比较的起始位置
            q=B->next; //指针 q 回到链表 B 中第一个数据结点位置 
        }
    }
    if(q==NULL)//若循环结束后 q 指针为空，则证明比较成功，返回 true 
        return true;
    else //若循环结束后 q 指针不为空，则证明比较失败，返回 false 
        return false;
}时间复杂度和空间复杂度分别为：O(mn)和O(1)

24.判断单链表是否有环

题目：通常单链表尾结点指针域为 NULL，而单链表有环，是指单链表最后一 个结点的指针指向了链表中的某个结点。请设计一个算法，判断一个带头结点的 单链表 L 是否有环，如果有环，返回环的入口结点位置，如果没有，返回 NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LNode *FindLoop(LinkList L){
    if(L->next=NULL)//若链表为空，则直接返回 NULL 
    	return NULL;
    LNode *fast=L,*slow=L; //定义两个快、慢指针，并进行初始化 
    while(fast!=NULL&&fast->next!=NULL){//考虑结点数有奇偶两种情况
        slow=slow->next; //慢指针每次遍历走一步 
        fast=fast->next->next;//快指针每次遍历走两步
        if(fast==slow)//若快慢两个指针指向了同一位置，则证明链表 L 有环 
            break;//单链表有环，直接跳出循环
    }
    if(fast==NULL||fast->next==NULL)//若正常循环结束，则单链表没环 return NULL;
        return NULL;
    LNode *p=L,*q=slow;//定义遍历指针 p 和 q 
    while(p!=q){//循环寻找环的入口结点
        p=p->next;
        q=q->next;
    }//返回环入口结点位置
    return p;
} 时间复杂度和空间复杂度分别为：O(n)和O(1)

25.将一个循环单链表链接到另一个循环单链表之后

题目：有两个带头结点的非空循环单链表 h1 和 h2，请设计一个算法，将链表 h2 链接到链表 h1 之后，要求链接后的链表仍是一个带头结点的循环单链表。

1
2
3
4
5
6
7
8
9
10
11
LinkList Link(LinkList h1,LinkList h2){
    LNode *p=h1,*q=h2; //定义遍历指针 p 和 q，遍历链表 h1 和 h2 
    while(p->next!=h1)//遍历链表 h1，找出该链表的尾结点
        p=p->next;
    while(q->next!=h2)//遍历链表 h2，找出该链表的尾结点 
        q=q->next;
    p->next=h2->next; //链表 h1 的尾结点链接到链表 h2 的第一个数据结点 
    q->next=h1; //链表 h2 的尾结点链接到链表 h1 的头结点
    free(h2); //删除链表 
    h2 的头结点 return h1; //返回新链表的头指针
}时间复杂度和空间复杂度分别为：O(m+n)和O(1)

26.一个循环单链表按结点值类型分解为三个循环单链表

题目：有一个带头结点的循环单链表L，链表L中含有三类字符的数据元素(如： 字母字符、数字字符和其它字符)，请设计一个算法，将链表 L 拆分为三个带头 结点的循环单链表，其中每个循环单链表均只含一类字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Split(LinkList L,LinkList &A,LinkList &B,LinkList &C){
    if(L->next=NULL;)//若链表为空表，则直接结束函数
        return 0;
    A=(LinkList)malloc(sizeof(LNode)); //创建 A 表头结点 
    B=(LinkList)malloc(sizeof(LNode)); //创建 B 表头结点 
    C=(LinkList)malloc(sizeof(LNode)); //创建 C 表头结点
    LNode *p=L->next,*ra=A,*rb=B,*rc=C; //定义遍历指针 p 和三个表的尾指针 
    while(p!=L){
        if((p->data>='A'&&p->data<='Z')||(p->data>='a'&&p->data<='z')){
            ra->next=p;//遍历结点数据域为字母，则将遍历结点尾插到 A 表 
            p=p->next;//更新 A 表尾指针
        }
        else if(p->data>='0'&&p->data<='9'){
            rb->next=p; //遍历结点数据域为数字，则将遍历结点尾插到 B 表 
            rb=p; //更新 B 表尾指针
        }
        else{
            rc->next=p;//遍历结点数据域为其它字符，则将遍历结点尾插到 C 表 
            rc=p; //更新 C 表尾指针
        }
        p=p->next; //更新遍历指针，继续遍历 
    }
    ra->next=A; //A 表尾结点指针域指向头结点 
    rb->next=B; //B 表尾结点指针域指向头结点 
    rc->next=C; //C 表尾结点指针域指向头结点 
    free(L); //删除链表 L 的头结点
}//时间复杂度和空间复杂度分别为：O(n)和O(1)

27.删除不带头结点单链表中的最小值结点

题目：有一个不带头结点的单链表 L，L 中各个结点的值都不相同，请设计一 个算法，删除链表 L 中的最小值结点。

  • 方法一（处理第一个数据结点时进行特殊考虑）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Del_Min(LinkList &L){//函数内可能改变头指针 L，所以需要加引用 
    if(L==NULL)
        return;
    LNode *pre,*p=L; //定义遍历指针 p 及其前驱指针 pre
	LNode *minpre,*minp=p; //定义最小值记录指针 minp 及其前驱指针 minpre 
    while(p!=NULL){//遍历该链表
        if(p->data<minp->data){ //判断遍历结点是否小于所记录的最小值结点 
            minp=p;//若遍历结点值更小，则更新最小值结点位置 
            minpre=pre;
        }
        pre=p;//遍历指针继续遍历
        p=p->next;
    }
    if(minp==L){ //如果链表中第一个数据结点是最小值结点，则需特殊考虑 
        L=L->next;//更新头指针位置
        free(L);//释放最小值结点空间
    }
    else{//如果链表最小值结点不是第一个数据结点，则正常删除 
        minpre->next=pre->next;//删除最小值结点
        free(minp);//释放最小值结点空间
    }
} //时间复杂度和空间复杂度分别为：O(n)和 O(1)
  • 方法二（先自行创建头结点，完成题目要求后再删除所创建的头结点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Del_Min(LinkList &L){
    if(L==NULL)
        return;
    LinkList head=(LinkList)malloc(sizeof(LNode)); //创建头结点
    head->next=L;
    LNode *pre,*p=L; //定义遍历指针 p 及其前驱指针 pre
	LNode *minpre,*minp=p; //定义最小值记录指针 minp 及其前驱指针 
    while(p!=NULL){ //遍历该链表
        if(p->data<minp->data){//判断遍历结点是否小于所记录的最小值结点
            minp=p;//若遍历结点值更小，则更新最小值结点位置
            minpre-=pre;
        }
        pre=p;//遍历指针继续遍历 
        p=p->next;
    }
    minpre->next=minp->next;//遍历结束，删除最小值结点 
    free(minp);//释放最小值结点空间
    L=head->next;//更新头指针（第一个数据结点可能为最小值结点已被删除） 
    free(head); //删除创建的头结点
} //时间复杂度和空间复杂度分别为：O(n)和O(1)

28.不带头结点单链表循环右移k个位置

题目：设将n(n>1)个整数存放到不带头结点的单链表L中，设计算法将L中保存的序列循环右移k(0<k<n)个位置。例如,若k=1,则将链表{0，1，2，3}变为 {3，0，1，2}

1
2
3
4
5
6
7
8
9
10
11
12
13
void Move_k(LinkList &L,int k){
    LNode *p=L; //定义遍历指针 p 并初始化
    int len=1; //定义变量 len，计算链表长度
    while(p->next!=NULL){ //计算链表长度并找到链表中尾结点位置
        p=p->next;
        len++;
    }
    p->next=L;//将链表改为不带头结点的循环单链表
    for(int i=0;i<len-k;i++)//原链表循环右移，寻找新链表尾结点 
        p=p->next;
    L=p->next;//更新链表头指针
    p->next=NULL; //尾结点指针域置空
}时间复杂度和空间复杂度分别为：O(n)和O(1)

29.计算不带头结点单链表的最大孪生和

题目：设有一个不带头结点的长度为n（n为偶数）的非空单链表,且结点值都大于0,设计算法求这个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和,对于第i个结点（从0开始）,其孪生结点为第n-i-1个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int MaxSum(LinkList L){
    LNode *slow=L,*fast=L->next; //定义快慢双指针并初始化 
    while(fast!=NULL&&fast->next!=NULL){
        slow=slow->next;
        fast=fast->next->next;
    }
    LNode *p=slow->next,*q; //定义遍历指针 p 和防断链指针 q
    slow->next=NULL; //将链表从中间分开
    while(p!=NULL){//将链表中后半部分结点挨个头插到前半部分结点的末尾
        q=p->next;//防断链指针记录下一个遍历结点位置
        p->next=slow->next; //头插法核心操作 
        slow->next=p;
        p=q; //更新遍历指针到下一个遍历结点位置
    }
    p=L,q=slow->next;//重新初始化遍历指针，使 p，q 分别遍历链表前后两部分
    int max=p->data+q->data;//定义变量 max，记录已遍历结点中的最大孪生和
    while(q!=NULL){ //遍历该链表
        if((p->data+q->data)<max)//若遍历结点孪生和更大，则更新 max 
            max=p->data+q->data;
        p=p->next;//遍历指针继续遍历 
        q=q->next;
    }
    return max; //遍历结束后，返回该链表的最大孪生和
}时间复杂度和空间复杂度分别为：O(n)和O(1)

30.约瑟夫环

题目：（约瑟夫环）有n个人围成一个圈，他们的编号为1～n。现在要求从第1个人开始报数，数到m的人出列，出列后的下一个人继续从1开始报数，同样数到m的人出列，一直重复此过程，直到圈中只剩下最后一个人，返回其编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Josephus(LinkList L,int m){
    LNode *p=L,*pre=L;//定义遍历指针及其前驱指针
    while(pre->next!=L) //pre 指针初始化到遍历结点的前驱，即链表的尾结点 
        pre=pre->next;
    while(p->next!=p){ //直到链表中还剩最后一个结点，结束循环 
        for(int i=1;i<m;i++){//循环报数
            pre=p;
            p=p->next;
        }
        pre->next=p->next; //数到 m 的人出列 
        free(p); //删除出列的结点
        p=pre->next;//更新遍历指针位置，重新报数
    }
    return p->data;//返回最后一个结点的编号
}时间复杂度和空间复杂度分别为：O(mn)和O(n)

31.双链表的结构体定义

1
2
3
4
typedef struct DNode{
	int data; //根据结点存储元素的类型选择数据域的数据类型 
    struct DNode *prior,*next; //结点的前驱指针和后继指针
}DNode,*DLinkList;

32.有序双链表插入一个新结点后依然有序

题目：在一个带头结点的非递减有序双链表中插入一个值为 x 的新结点，使得 插入新结点后链表依然非递减有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
viod LintInsert(DLinkList L,int x){
    DNode *pre=L,*p=L->next;//定义遍历指针 p 和前驱指针 pre 
    while(p!=NULL){//遍历该链表
        if(p->data>x)//若 p 指向结点数据域大于 x，则找到插入位置 
            break;//找到插入位置，跳出循环
        pre=p;//没有找到插入位置，继续遍历 
        p=p->next;
    }
    DNode *s=(DLinkList)malloc(sizeof(DNode)); //创建新结点 
    s->data=x;//为新结点数据域赋值
    s->next=pre->next;//更新插入结点的后继指针
    if(p->next!=NULL) //结点插入位置不是链表最后，则更新后继结点前驱指针 
        pre->next->prior=s;
    s->prior=pre;//更新插入结点的前驱指针 
    pre->next=s; //更新前驱结点的后继指针 
}时间复杂度和空间复杂度分别为：O(n)和O(1)

33.删除双链表中的最小值结点

题目：有一个带头结点的双链表 L，L 中各个结点的值都不相同，请设计一个 算法，删除链表 L 中的最小值结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Del_Min(DLinkList L){
    if(L->next==NULL)//若链表为空表，则直接结束函数 
        return;
    DNode *minpre=L,*minp=L->next; //记录已遍历结点中最小值结点及其前驱 
    DNode *pre=L,*p=L->next; //定义遍历指针 p 及其前驱指针 pre 
    while(p!=NULL){//遍历该链表
        if(p->data<minp->data){//判断遍历结点的值是否小于记录的最小值结点 
        	minp=p; //若遍历结点值更小，则更新最小值结点位置
        	minpre=pre;//更新最小值结点前驱结点位置
    	}
        pre=p; //继续遍历 
        p=p->next;
    }
    minpre->next=minp->next;//将最小值结点从链表中删除 
    if(minp->next!=NULL)//若最小值结点不是尾结点，
    	minp->next->prior=minpre; //则更新最小值结点后继结点的前驱指针
    free(minp); //释放最小值结点空间
}时间复杂度和空间复杂度分别为：O(n)和O(1)

34.判断循环双链表是否对称

题目：请设计一个算法，判断带头结点的循环双链表 L 是否对称

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Symmetry(DLinkList L){
    if(L->next==L||L->next->next==L)//链表为空表或只有一个数据结点则对称 
        return true;
    DNode *p=L->next,*q=L->prior; //两指针以头结点为中心分别遍历链表两侧 
    while(p!=q&&p->next!=q){//需考虑结点个数是奇数还是偶数
        if(p->data==q->data){//若两遍历结点数据域相同则需继续遍历 
            p=p->next;
            q=q->prior;
        }
        else//若两遍历结点数据域不同，则证明循环双链表不对称 
            return false;
    }
    return true;//正常跳出循环则证明遍历结点数据域均相同，循环双链表对称
}时间复杂度和空间复杂度分别为：O(n)和O(1)

35.将双链表中的最大值结点移动到最前面

题目：有一个带头结点的双链表 L，L 中各个结点的值都不相同，请设计一个算法，将链表 L 中的最大值结点移动到最前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Move_Max(DLinkList L){
    if(L->next==NULL)
        return;
    DNode *maxpre=L,*maxp=L->next; //记录已遍历结点中最大值结点及其前驱 
    DNode *pre=L,*p=L->next; //定义遍历指针 p 及其前驱指针 pre 
    while(p!=NULL){
        if(p->data>maxp->data){
            maxp=p; //若遍历结点值更大，则更新最大值结点位置
            maxpre=pre; //更新最大值结点前驱结点位置
        }
    }
    if(maxp==L->next) //若最大值结点已经在链表最前面，则结束函数 
        return;
    DNode *q=maxp->next; //定义指针q记录最大值结点的后继结点位置 
    maxpre->next=q;/前驱结点的后继指针指向后继结点
    if(q!=NULL)//判断最大值结点有无后继结点
        q->prior=maxpre;//后继结点的前驱指针指向前驱结点
    q=L->next;//将最大值结点移动到链表最前面
    maxp->next=q;
    q->prior=maxp;
    L->next=maxp;
    maxp->prior=L;
}时间复杂度和空间复杂度分别为：O(n)和O(1)

36.双链表中结点按查找频度递减顺序排列

题目：设有一个带头结点的非循环双链表 L，其每个结点除了有 prior、data 和 next 域外，还有一个访问频度域 freq，其值均初始化为 0。L中各个结点的值都 不相同，每当在链表中执行一次 Locate(L,x)运算时，令值为 x 的结点中 freq 域的值增 1，并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结 点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)函数，返回找到结点的地址，类型为指针型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
DNode *Locate(DLinkList L,int x){
    if(L->next==NULL)//若链表为空表，则直接结束函数 
        return NULL;
    DNode *pre=L,*p=L->next; //定义遍历指针p及其前驱指针pre 
    while(p!=NULL){//遍历该链表
        if(p->data==x)//查找链表中值为 x 的结点 
            break;
        pre=p; //继续遍历 
        p=p->next;
    }
    if(p==NULL) //若链表中没有值为 x 的结点，则直接结束函数 
        return NULL;
    p->freq++;//找到值为 x 的结点，让其 freq 域加一
    if(p->prior==L)//若该结点就在链表最前方 
        return p;
    DNode *q=p->next; //定义指针 q 记录查找结点后继 
    pre->next=q; //将查找结点从链表中摘下
    if(q!=NULL)
        q->prior=pre;
    pre=L,q=L->next; //初始化 pre 指针和 q 指针 
    while(q!=NULL){//遍历链表
        if(q->freq<p->freq) //寻找结点的插入位置 
            break;
        pre=q;
        q=q->next;
    }
    p->next=q;//插入值为 x 的结点 
    q->prior=p;
    p->prior=pre;
    pre->next=p;
    return p;//返回结点指针
}时间复杂度和空间复杂度分别为：O(n)和O(1)

37.递归查找不带头结点单链表中的最小值结点

题目：有一个不带头结点的单链表 L，L 中各个结点的值都不相同，请设计一个递归算法，查找链表 L 中的最小值结点

1
2
3
4
5
6
7
8
9
LNode *Find_Min(LinkList L){
    if(L==NULL||L->next=NULL)
        return L;
    LNode *p=Find_Min(L->next); //指针 p 记录后续链表的最小值结点位置 
    if(p->data<L->data)//后续链表的最小值结点与当前数据结点进行比较
        return p;//返回值较小结点指针
    else
        return L;
}时间复杂度和空间复杂度分别为：O(n)和O(n)