[线性表](7)题集_1

294
[ 数据结构 ] [ 线性表 ]

基本内容：

  • 线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法
  • 线性表的两类存储结构（顺序的和链式的）上基本操作的实现
  • 稀疏多项式的抽象数据类型定义、表示和加法的实现

线性表的逻辑结构特性是数据元素之间存在着线性关系。

在计算机中表示这种关系的两类不同的存储结构分为：顺序存储结构和链式存储结构

前者表示线性表简称为顺序表，后者表示线性表简称为链表

顺序表：

  • 静态顺序表：内存空间固定的，表的大小固定的，无法改变
  • 动态顺序表：内存空间由用户自定义，可随着数据增大而重新分配

链表：

  • 单向动态链表：只有一个指向后继结点的指针，结点空间由用户分配
  • 双向动态链表：有两个指针，一个指向前置结点，一个指向后继结点，结点空间由用户分配
  • 循环链表：尾结点的指针域指向头结点
  • 静态链表：结合了顺序表易访问和链式表易操作的优点，通过一个整型数据游标来进行结点相链，操作途中要明确“备用表”和“数据表”的关系。空间由用户指定（在C语音里面，利用结构数组来表示）

基础知识题：

1.描述以下三个概念的区别：

  • 头指针
  • 头结点
  • 首元节点

头指针：是指向表头数据的指针，它用于访问整个链表，存放整个链表的基址，在链表操作里边，头指针是不可或缺的角色

头结点：通常指的是头指针指向的结点，头结点可带数据可不带数据，在不带数据的情况下，头结点的指针域指向首元结点，头结点用于链接整个链表

首元结点：位于表头第一个带数据的结点，通常指头结点（不带数据）后的第一个结点，通过它对链表进行一系列操作。

2.填空题：

在顺序表中插入或删除一个元素，需要平均移动n/2个元素，具体移动的元素个数与需要删除或插入元素的位置有关

顺序表中逻辑相邻的元素的物理位置也紧邻，单链表中逻辑相邻的元素的物理位置不紧邻

在单链表中，除了首元结点外，任一节点的存储位置由它 前置结点的指针域指示

在单链表中设置头结点的作用是：用于链表结点的访问，易与控制整个链表，无需改变头指针的指向，链表逻辑清晰

3.在什么情况下用顺序表比链表好

在数据无需进行大规模的增删操作的时候，利用顺序表方便数据的引用以及修改，而在数据需要进行增删等操作的情况下，链表的存储方式比只需修改指针域的指向来修改结点之间的关系，而顺序表则需要大规模的移动数据

在已知数据的情况下利用顺序存储结构能更好的控制数据，而在未知的情况下利用链表能更好的控制数据

4.对以下单链表分别执行下列各程序段，并画出结果示意图

img

  • Q=P->next
  • L=P->next
  • R->data=P->data
  • R->data=P->next->data
  • P->next->next->next->data=P->data
  • T=P
    • while(T!=NULL){T->data=T->data*2; T=T->next}
  • T=P
    • while(T->next!=NULL){T->data=T->data*2; T=T->next}

第一句，将Q指针指向P的后继结点

img

第二句，将L指针指向P的后继结点

img

第三句，将P指针指向的结点的数据域赋值给R指针指向结点的数据域

img

第四句，将P指向结点的后继结点的数据域赋值给R指针指向结点的数据域

img

第五句，将P指针指向结点数据域赋值给P第三个后继结点的数据域

img

第六句，将T指向P，当T指向的结点不为空的时候，将T指向结点的数据域*2，T指向下一个结点，继续循环

img

第七句，将T指向P，判断T的下一结点是否为空，将T指向结点的数据域*2，T指向下一个结点，继续循环

img

5.画出执行下列语句后各指针及链表的示意图

L = (LinkList)malloc(sizeof(LNode));
P = L;
for (i = 1; i <= 4; i++)
{
    P->next = (LinkList)malloc(sizeof(LNode));
    P = P->next;
    P->data = i * 2 - 1;
}
P->next = NULL;
for (i = 4; i >= 1; i--)
{
    Ins_LinkList(L, i + 1， i * 2);
}
for (i = 1; i <= 3; i++)
{
    Del_LinkList(L, i);
}

先分析下题目：L作为头结点同时也作为头指针，程序先定义一个操作指针P让他指向L

再不断分配空间，一共分配了四个结点，链接至P后，链接完毕后，P已指向表尾，让P的指针域为空，程序示意图如下：

img

然后进入第二个循环，调用4次Ins_LinkList函数，该操作算法如下：

void Ins_LinkList(LinkList L, int j, int e)
{
    LinkList P, node;
    P = L;
    for (int i = 1; i < j; i++)
    {
        P = P->next;
    }
    node = (LinkList)malloc(sizeof(LNode));
    node->next = P->next;
    P->next = node;
    node->data = e;
}

不断在i+1的位置插入值为i*2的结点

  • 第一次：插入位置为5，插入值为8
  • 第二次：插入位置为4，插入值为6
  • 第三次：插入位置为3，插入值为4
  • 第四次：插入位置为2，插入值为2

运算后示意图如下：

img

后进入第二个循环语块调用三次Del_LinkList函数

删除第i个结点

完成算法如下：

void Del_LinkList(LinkList L, int i)
{

    LinkList p, s;
    p = L;
    s = L->next;
    for (int j = 1; j <= i && s != NULL; j++)
    {
        p = s;
        s = s->next;
    }

    p->next = s->next;
    free(s);
}

操作完成后示意图如下：

img

6.已知L表示无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列

  • 在P结点后插入S结点的语句序列是：

    • S->next=P->next;
    • P->next=S;
  • 在P结点前插入S结点的语句序列是：
    • Q=P;
    • P=L;
    • while(P->next!=Q)P=P->next;
    • S->next=P->next;
    • P->next=S;
  • 在表首插入S结点的语句序列是：
    • S->next=L;
    • L=S;
  • 在表尾插入S结点的语句序列是：
    • while(P->next!=NULL)P=P->next;
    • P->next=S;
    • S->next=NULL;
  • 从下列语句中选出
    1. P->next=S;
    2. P->next=P->next->next;
    3. P->next=S->next;
    4. S->next=P->next;
    5. S->next=L;
    6. S->next=NULL;
    7. Q=P;
    8. while(P->next!=Q)P=P->next;
    9. while(P->next!=NULL)P=P->next;
    10. P=Q;
    11. P=L;
    12. L=S;
    13. L=P;

7.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列

  • 删除P结点的直接后继结点的语句序列是
    • Q=P->next;
    • P->next=P->next->next;
    • free(Q);
  • 删除P结点的直接前驱结点的语句序列是
    • Q=P;
    • P=L
    • while(P->next!=Q)P=P->next;
    • Q=P;
    • P=L
    • while(P->next!=Q)P=P->next;
    • P->next=P->next->next;
    • free(Q);
  • 删除P结点的语句序列是
    • Q=P;
    • P=L
    • while(P->next!=Q)P=P->next;
    • P->next=P->next->next;
    • free(Q);
  • 删除首元结点的语句序列是
    • P=L
    • P=P->next;
    • Q=P;
    • P=L
    • P->next=P->next->next;
    • free(Q);
  • 删除尾元结点的语句序列是
    • while(P->next->next!=NULL)P=P->next;
    • P->next=P->next->next;
    • P=P->next;
    • Q=P;
    • free(Q);
  1. P=P->next;
  2. P->next=P;
  3. P->next=P->next->next;
  4. P=P->next->next;
  5. while(P!=NULL)P=P->next;
  6. while(Q->next!=NULL)P=P->next;
  7. while(P->next!=Q)P=P->next;
  8. while(P->next->next!=NULL)P=P->next;
  9. Q=P;
  10. Q=P->next;
  11. P=L
  12. L=L->next;
  13. free(Q);

8.已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列

  • 在P结点后插入S结点的语句序列是
    • S->priou=p;
    • S->next=P->next;
    • P->next->priou=S;
    • p->next=S;
  • 在P结点前插入S结点的语句序列是
    • S->priou=P->priou;
    • P->priou->next=S;
    • S->next=P;
    • p->priou=S;
  • 删除P结点的直接后继结点的语句序列是
    • Q=P->next;
    • P->next=P->next->next;
    • P->next->priou=P;
    • free(Q);
  • 删除P结点的直接前驱结点的语句序列是
    • Q=P->priou;
    • P->priou=P->priou->priou;
    • P->priou->next=P;
    • free(Q);
  • 删除P结点的语句序列是
    • p->priou->next=p->next;
    • P->next->priou=P->priou;
    • free(p);
  1. P->next=P->next->next;
  2. P->priou=P->priou->priou;
  3. p->next=S;
  4. p->priou=S;
  5. S->next=P;
  6. S->priou=p;
  7. S->next=P->next;
  8. S->priou=P->priou;
  9. p->priou->next=p->next;
  10. P->priou->next=P;
  11. P->next->priou=P;
  12. P->next->priou=S;
  13. P->priou->next=S;
  14. P->next->priou=P->priou;
  15. Q=P->next;
  16. Q=P->priou;
  17. free(p);
  18. free(Q);

9.简述以下算法的功能：

Status A(LinkedList L)//L是无表头结点的单链表
{
    if (L && L->next)
    {
        Q = L;
        L = L->next;
        P = L;

        while (P->next)
        {
            P = P->next;
        }
        P->next = Q;
        Q->next = NULL;
    }
    return OK
}

这个算法一看就知道，将表头插到表尾，更新头指针指向。

void BB(LNode* s, LNode* q)
{
    p = s;
    while (p->next != q)
    {
        p = p -> next;
    }

    p->next = s;
}
void AA(LNode* pa, LNode* pb)
//pa和pb分别指向单循环链表中的两个结点
{
    BB(pa, pb);
    BB(pb, pa);
}

这个算法，就是将一个循环链表分割成两个循环链表

第一个函数的作用就将q之前的结点链接到头指针指向的节点，第二个函数的作用就是通过两个结点调用第一个函数，起到分割链表作用。

算法设计题：

按书本要求，以下算法涉及的顺序表和线性链表的类型定义如下：

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
    ElemType* elem;//存储空间的基址
    int length;//当前长度
    int listsize;//当前分配的空间长度
}SqList;

typedef struct LNode
{
    ElemType data;
    struct LNode* next
}LNode, * LinkList;//链表类型

10.指出下列算法中的错误和低效(费时)之处，并将它改写为一个既正确又高效的算法：

Status DeleteK(SqList& a, int i, int k)
//本过程从顺序表a中删除以第i个元素起的k个元素
{
    if (i < || k<0 || i + k>a.length)
    {
        return INFEASIBLE;//参数不合法
    }
    else
    {
        for (count = 1; count < k; count++)
        {
            for (j = a.length; j >= i + 1; j--)
            {
                a.elem[j - 1] = a.elem[j];
            }
            a.length--;
        }
    }
}

错误有两处：

  • 参数不合法的判别条件不完整，合法的入口参数条件为：
    • (0<i<a.length)||(0<=k<=a.length-i)
  • 第二个错误是第二个循环语块中元素前移的次序错误
  • 低效之处就是每次删除一个元素

时间复杂度取决于需要删除的次数和表的长度，正确的算法如下所示（完成测试代码）

#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int* elem;
    int length;
    int listsize;
}SqList;

SqList S;

void DeleteK(SqList *S, int i, int k);
void InfoSqList(SqList);
int main()
{

    S.elem = (int*)malloc(sizeof(int) * 100);
    S.length = 0;
    S.listsize = 100;
    while (S.length < 10)
    {
        InfoSqList(S);
        S.length++;
        S.listsize--;
    }

    for (int i = 0; i < S.length; i++)
    {
        printf("%d ", S.elem[i]);
    }

    int i, e;
    printf("\n请输入需要删除的起始位置：");
    scanf("%d", &i);
    printf("请输入需要删除的元素个数：");
    scanf("%d", &e);

    DeleteK(&S, i, e);

    for (int i = 0; i < S.length; i++)
    {
        printf("%d ", S.elem[i]);
    }

    system("pause");
    return 0;
}
void InfoSqList(SqList S)
{
    scanf("%d", &S.elem[S.length]);
}

void DeleteK(SqList *S, int i, int e)
{
    if (0 > i > S->length || 0 > e > S->length - i)
    {
        printf("删除位置或元素个数不合法");
        exit(0);
    }
    for (int k = i + e; k <= S->length; k++)
    {
        S->elem[k - e] = S->elem[k];
    }
    S->length = S->length - e;
    S->elem[S->length] = NULL;

}

11.设顺序表va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性

这题，有序，递增，那么一想到，二分查找，找到正确位置后插入：完整算法如下

int ListInsert(SqList *S, int e)
{
    int len = S->length / 2;
    int r = 0;
    int l = S->length;

    if (S->length<0)
    {
        printf("插入位置不合法\n");
        return -1;
    }

    if (S->length >= S->listsize)
    {
        S->elem = (int*)malloc(sizeof(int) * (100 + 10));
        S->listsize += 10;
    }

    if (e > S->elem[S->length-1])
    {
        S->elem[S->length] = e;
        S->length++;
        S->listsize--;
        return 0;
    }
    if (S->elem[0] > e)
    {
        for (int k = S->length; k >= 0; k--)
        {
            S->elem[k] = S->elem[k - 1];
        }
        S->elem[0] = e;
        S->length++;
        S->listsize--;
        return 0;
    }

    while (r <= len && len <= l)
    {
        if (S->elem[len - 1] <= e && e <= S->elem[len])
        {
            for (int k = S->length; k >= len; k--)
            {
                S->elem[k] = S->elem[k - 1];
            }
            S->elem[len] = e;
            S->length++;
            S->listsize--;
            break;
        }
        else if (S->elem[len] > e)
        {
            len = len / 2;
        }
        else
        {
            len = (len + l) / 2;
        }       
    }
}

12.设A=(a1,....am)和B=(b1,...,bn)均为顺序表，A’和B’分别为A和B中出去最大共同前缀后的子表，例如：

  • A=（x，y，y，z，x，z）
  • B=（x，y，y，z，y，x，x，z）

则两者中的最大的共同前缀为（x，y，y，z），在两表中除去最大共同前缀的子表分别为A’=（x，z）和B’=（y，x，x，z），出现一下几种结果：

  • 若A’=B’=空表，则A=B
  • 若A’=空表，而B！=空表，或者两则均不为空表，且A’的首元小于B’的首元，则A<B，否则A>B

试着写一个比较A，B大小的算法

这题大水题，用指针走到不相等的地方比较就好了，算法如下：

int CmpSqList(SqList A, SqList B)
{
    int a = 0, b = 0;
    while (A.elem[a] != NULL && B.elem[b] != NULL)
    {
        if (A.elem[a] < B.elem[b])
        {
            printf("\nA<B");
            return -1;
        }
        if (A.elem[a] > B.elem[b])
        {
            printf("\nA>B");
            return 1;
        }
        a++;
        b++;
    }

    if (A.elem[a] == NULL && B.elem[b] == NULL)
    {
        printf("\nA=B");
        return 0;
    }

    if (A.elem[a])
    {
        printf("\nA>B");
        return 1;
    }

    if (B.elem[b])
    {
        printf("\nA<B");
        return -1;
    }
}

13.试写一算法在带表头结点的单链表结构上实现线性表操作LOCATE(L,X)

这题我的理解是在L表中找出X

LinkList LocateList(LinkList L, int x)
{
    LinkList P;
    P = L->next;
    while (P != NULL && P->data != x)
    {
        P = P->next;
    }
    if (P == NULL)
    {
        printf("未找到该元素");
        exit(0);
    }
    else
    {
        return P;
    }
}

14.试写一算法在带表头结点的单链表结构上实现线性表操作LENGTH(L)

int LengthList(LinkList L)
{
    LinkList P;
    int count = 0;
    P = L->next;
    while (P != NULL && P->data != x)
    {
        P = P->next;
        count++; 
    }
    return count;
}

15.已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n，试写一算法将这两个链表链接到一起（其一链表的首元节点连接到另一链表的尾结点后），假设指针hc指向链接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算，请分析你的算法的时间复杂度

int ConnectList(LinkList A, LinkList B)
{
    LinkList ha, hb, hc;
    ha = A;
    hb = B;
    if (ha->next == NULL && hb->next == NULL)
    {
        return 0;
    }
    while (ha->next != NULL)
    {
        ha = ha->next;
    }
    ha->next = hb->next;
    free(hb);
    hc = ha;
}

时间复杂度与其一链表的长度有关，需要找到链表的表尾才能进行链表，在上述算法中，时间复杂度为O（m）

16.已知指针la和lb分别指向两个无头结点单链表中的首元结点，下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之前，试问此算法是否正确，若有错，请改正

Status DeleteAndInsertSub(LinkList la, LinkList lb, int i, int j, int len)
{
    if (i < 0 || j < 0 || len < 0)
    {
        return INFEASIBLE;
    }
    p = la; k = 1;
    while (k < i)
    {
        p = p->next;
        k++;
    }
    q = p;
    while (k <= len)
    {
        q = q->next;
        k++;
    }
    s = lb;
    k = 1;
    while (k < j)
    {
        s = s->next;
        k++;
    }
    s->next = p;
    q->next = s->next;
    return OK;
}

讲真，看到这算法后，我脑海里边出现的就全是错误

入口条件，首先要规划边界，删除的总数必须小于链表的长度，而因为是不带头节点的，所有首元结点我喜欢称为第一结点，游标都从1,开始，则i，j，len，都不能小于1，主要思路是分割其一结点后，将分割出来的链表链接到另一链表的指定位置，需要保存：

  • 分割链表的头，尾
  • 待分割的前驱，后置
  • 待插入的前驱，后置

还需要注意特殊值：插入到表头和表尾

完整算法如下：

int DeleteAAndInsertSub(LinkList *la, LinkList *lb, int i, int j, int len)
{
    int k;
    LinkList p, s, p1, s1, a, b;
    if (i <= 0 || j <= 0 || len <= 0 || la[i + len] == NULL)
    {
        exit(0);
    }
    k = 1;
    p = *la;
    while (k < i)
    {
        p = p->next;
        k++;
    }
    p1 = p;
    a = p->next;//保存删除的头
    k = 1;
    while (k <= len)
    {
        p = p->next;
        k++;
    }
    s = p;//保存删除的尾
    p1->next = p->next;

    b = *lb;
    if (j == 1)
    {
        s->next = b;
        *lb = a;
    }
    else
    {
        k = 1;
        while (k < j - 1)//从1开始，j-1是找到它的前驱
        {
            b = b->next;
            k++;
        }
        s1 = b->next;
        b->next = a;
        s->next = s1;
    }
}

17.试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较

不带头结点：

需要考虑的是，插入的位置是头还是尾，不带头结点我喜欢从1开始，那么需要找到它的前驱和后置，然后前驱链接插入结点，插入结点链接后置，判决条件是不能小于一，也不能大于表长+1

完整代码：

int InsertList(LinkList *L, int i, int b)
{
    int count = 1;
    LinkList s = *L, p = s->next, node;
    if (i <= 0)
    {
        printf("插入位置不合法");
        exit(0);
    }
    if (i == 1)
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        node->next = s;
        *L = node;
        return 0;
    }

    while (s != NULL && count < i - 1)
    {
        s = p;
        p = p->next;
        count++;
    }
    if (s == NULL)
    {
        printf("插入位置不合法");
    }
    else
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        node->next = p;
        s->next = node;
    }

}

带头结点：

从0开始计数，不需要改变头指针位置，头指针后链接首元结点。

判决条件，不能小于1，也不能大于表长+1。完整代码：

int InsertList(LinkList *L, int i, int b)
{
    int count = 0;
    LinkList s = *L, p = s->next, node;
    if (i <= 0)
    {
        printf("插入位置不合法");
        exit(0);
    }
    if (i == 1)
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        s->next = node;
        node->next = p;
        return 0;
    }

    while (s != NULL && count < i - 1)
    {
        s = p;
        p = p->next;
        count++;
    }
    if (s == NULL)
    {
        printf("插入位置不合法");
        exit(0);
    }
    else
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        node->next = p;
        s->next = node;
    }

}

18.同上要求，完成DELETE算法

int LenthList(LinkList L)
{
    int count = 1;
    LinkList p = L;
    if (L == NULL)
    {
        return 0;
    }
    while (p->next != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

int DeleteList(LinkList* L, int i)
//删除L表中第i个位置
{
    if (0 >= i || i > LenthList(*L))
    {
        printf("删除位置不合法\n");
        return 0;
    }
    LinkList p,s;
    p = *L;
    s = (*L)->next;
    int count = 1;

    if (i == 1)
    {
        *L = s;
        free(p);
        return 0;
    }

    while (count < i - 1)
    {
        p = s;
        s = s->next;
        count++;
    }

    p->next = s->next;
    free(s);
}

同上所述，不带头结点的元素从1开始，当删除位置到表头的时候，需要改变头指针指向

带头结点：

int DeleteList(LinkList* L, int i)
//删除L表中第i个位置
{
    if (0 >= i || i > LenthList(*L))
    {
        printf("删除位置不合法\n");
        return 0;
    }
    LinkList p,s;
    p = *L;
    s = (*L)->next;
    int count = 0;

    if (i == 1)
    {
        p->next = s->next;
        free(s);
        return 0;
    }

    while (count < i - 1)
    {
        p = s;
        s = s->next;
        count++;
    }

    p->next = s->next;
    free(s);
}

相差不大，不需要改变头指针位置，单链表很好操作，都是基础题。我们看下一题：

总得来说：带头结点的首元结点位于头结点后，在指定位置插入和删除的时候位于第一位，而带头结点的首元节点就是头指针所指向的结点，位于第二位！

19.已知线性表中的元素以值递增有序排列，并以单链表做存储结构，试写一高效算法，删除表中所有值大于mink且小于maxk的元素(若表中存在满足条件的元素)同时释放被删除的结点空间，并分析你的算法的时间复杂度(注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同)

这道题需要注意两个点，一个是有序，一个是单链表，既然是链式存储，而且是动态带头结点的单链表，就不能二分查找，思路就是从首元节点开始，一个指针指向它的前驱，不断后移，知道满足mink的条件的数，利用一个指针指向这个数，继续后移，后移后释放刚刚满足条件的数，最后达到满足maxk元素的时候，将其链接起来，代码如下所示：

void MinkMaxkList(LinkList L, int i, int j)
{
    LinkList p, s, p1, P;
    s = L;
    p = L->next;
    while (p != NULL)
    {
        if (p->data > i && p->data < j)
        {
            p1 = p;
            p = p->next;
            free(p1);
            continue;
        }
        if (p->data >= j)
        {
            s->next = p;
            break;
        }
        s = p;
        p = p->next;
    }
    if (p == NULL)
    {
        s->next = NULL;
    }

}

20.同19题的条件，写一高效算法，删除表中所有值相同的多余元素（使得操作后的线性表所有值均不相同），同时释放被删的结点空间，并分析你的算法的时间复杂度

这道题我首先想的是，拿链表中的每一个数去往后边遍历，但是突然想到，这是一个有序链表，在蓝哥的指导下，用双指针也可以实现。

通用链表算法：

void DeleteEqualList(LinkList L)
//利用三个指针，一个快指针s，一个跟着快指针指向前驱p1
//一个慢指针p，不断去遍历
//时间复杂度与链表的元素有关，平均复杂度是O((2/n)n)
{

    LinkList p, s, p1;
    p = L->next;
    while (p != NULL)
    {
        p1 = p;
        s = p->next;
        while (s != NULL)
        {
            if (p->data == s->data)
            {
                p1->next = s->next;
                free(s);
                s = p1->next;
                continue;
            }
            p1 = s;
            s = s->next;
        }
        p = p->next;
    }
}

img

有序链表借鉴大佬的思想，算法如下：

void DeleteEqualList(LinkList L)
{

    LinkList p, s, p1;
    p = L->next;
    s = p->next;
    while (s)
    {
        if (p->data == s->data)
        {
            p1 = s;
            s = s->next;
            free(p1);
            p->next = s;
            continue;
        }
        p = s;
        s = s->next;
    }
}

时间复杂度仅仅为O(n)，因为只需要快指针s遍历一次链表

本文链接：

https://nullcode.fun/13.html
1 + 4 =
快来做第一个评论的人吧~