2024重生之回溯数据结构与算法系列学习（6）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

盛透侧视攻城狮

发布于 2025-05-19 18:10:43

11200

代码可运行

文章被收录于专栏：超前沿网络空间安全全栈学习宝典超前沿网络空间安全全栈学习宝典

运行总次数：0

代码可运行

（21）题目：单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是空的)。试编写算法判断单链表是否存在环。

1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释
3）说明你所设计算法的时间复杂度和空间复杂度。

解题思路：

>设置快慢指针

>用快的指针去追慢的指针

实现代码：

#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;               // 数据域
    struct LNode *next;    // 指向下一个节点的指针
} LNode, *LinkList;

// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0;
    LNode *r = L; // r指向链表的尾部
    while (cin >> val) // 循环输入值
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val; // 赋值
        r->next = s; // 尾插
        r = s; // 更新r为新插入的节点

        // 检查是否到达行尾
        if (cin.get() == '\n')
        {
            break;
        }
    }

    r->next = L; // 形成循环链表
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从第一个有效节点开始遍历
    while (p != L) // 遍历直到回到头节点
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next; // 移动到下一个节点
    }
    cout << endl; // 换行
}

// 检测链表是否有环
void LoopNode(LinkList &L)
{
    LNode *fast, *slow;    // 定义两个指针，快指针和慢指针
    fast = slow = L->next; // 都从链表的第一个有效节点开始

    // 同时遍历链表
    while (fast != NULL && fast->next != NULL) // 确保快指针不越界
    {
        slow = slow->next;       // 慢指针每次走一步
        fast = fast->next->next; // 快指针每次走两步

        // 如果快慢指针相遇，则说明链表有环
        if (fast == slow)
        {
            break;
        }
    }

    // 检查链表是否无环
    if (fast == NULL || fast->next == NULL)
    {
        cout << "链表无环" << endl; // 输出无环提示
        return;
    }

    cout << "链表有环" << endl; // 输出有环提示
}

int main()
{
    // 创建四个链表节点
    LinkList L1 = new LNode;
    LinkList L2 = new LNode;
    LinkList L3 = new LNode;
    LinkList L4 = new LNode;

    // 构建链表并使其形成环
    L1->next = L2; // L1指向L2
    L2->next = L3; // L2指向L3
    L3->next = L4; // L3指向L4
    L4->next = L2; // L4指向L2，形成环

    // 检测链表是否有环
    LoopNode(L1);
}

（22）题目：【已知一个带有表头结点的单链表，结点结构为datalink假设该链表只给出了头指针 list.在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0.

要求：

描述算法的基本设计思想.
描述算法的详细实现步骤。
根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++或 Java 语言实现),关键之处请给出简要注释。

解题思路：

>设置快慢指针

>利用两个指针的差

实现代码：

#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;               // 数据域
    struct LNode *next;    // 指向下一个节点的指针
} LNode, *LinkList;

// 尾插法构建链表
void TailInsert(LinkList &L)
{
    int val = 0;           // 用于存储输入的值
    LNode *r = L;         // r指向链表的尾部
    r->next = NULL;       // 初始化尾部指针

    // 循环输入链表节点的值
    while (cin >> val)
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 将输入值赋给新节点
        r->next = s;         // 将新节点连接到链表尾部
        r = s;               // 更新尾部指针为新节点
        r->next = NULL;      // 确保新节点的next指针为NULL

        // 检查输入是否到达行尾
        if (cin.get() == '\n')
        {
            break; // 如果是换行符，则停止输入
        }
    }
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从第一个有效节点开始遍历
    while (p) // 遍历链表
    {
        cout << p->data << '\t'; // 输出当前节点的数据
        p = p->next; // 移动到下一个节点
    }
    cout << endl; // 换行
}

// 查找链表中倒数第k个节点
void SearchK(LinkList &L, int k)
{
    LNode *p, *q; // 定义两个指针，分别是快指针p和慢指针q
    p = q = L->next; // 同时指向第一个有效节点

    int count = 0; // 计数器，用于统计节点数量
    while (p) // 遍历链表
    {
        // 计数，先找到第k个节点
        if (count < k)
        {
            count++; // 计数器加1
        }
        // 当到达第k个节点之后，慢指针开始移动
        else
        {
            q = q->next; // 慢指针移动到下一个节点
        }
        p = p->next; // 快指针移动到下一个节点
    }

    // 当快指针p到达链表尾部时，慢指针q指向的就是倒数第k个节点
    if (count < k) // 如果节点总数小于k
    {
        cout << "查找失败" << endl; // 输出查找失败提示
        return; // 结束函数
    }

    cout << q->data << endl; // 输出倒数第k个节点的数据
}

int main()
{
    LinkList L = new LNode; // 创建一个链表头节点
    L->next = NULL; // 初始化头节点的next指针

    TailInsert(L); // 调用尾插法构建链表

    SearchK(L, 3); // 查找倒数第3个节点并输出其数据
}

（23）题目：假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。strl1adstr2,ingbe设strl和str2分别指向两个单词所在单链表的头结点,链表结点结构为data next请设计一个时间上尽可能高效的算法,找出由 strl 和 str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置 p)。

要求：

给出算法的基本设计思想。
根据设计思想，采用 C 或 C++或 Java 语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度。

解题思路：

获取公共点

实现代码：

#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    char data;          // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;

// 头插法
void HeadInsert(LinkList &L)
{
    char val = '\0';
    // 读取输入，直到遇到换行符
    while (cin >> val)
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 更新头指针指向新节点

        if (cin.get() == '\n') // 如果读取到换行符，结束输入
        {
            break;
        }
    }
}

// 尾插法
void TailInsert(LinkList &L)
{
    char val = 0;
    LNode *r = L; // r指向链表的最后一个节点
    // 读取输入，直到遇到换行符
    while (cin >> val)
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 将当前尾节点的next指向新节点
        r = s;               // 更新r为新节点
        r->next = NULL;      // 新节点的next指向NULL

        if (cin.get() == '\n') // 如果读取到换行符，结束输入
        {
            break;
        }
    }
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // p指向链表的第一个节点
    while (p) // 遍历链表
    {
        cout << p->data << '\t'; // 输出当前节点数据
        p = p->next; // 移动到下一个节点
    }
    cout << endl; // 输出换行
}

// 查找两个链表的公共节点
void PublicNode(LinkList &LA, LinkList &LB)
{
    int lena = 0, lenb = 0;
    LNode *p = LA->next;

    // 计算LA的长度
    while (p)
    {
        lena++;
        p = p->next;
    }
    p = LB->next;

    // 计算LB的长度
    while (p)
    {
        lenb++;
        p = p->next;
    }

    LNode *longList, *shortList; // 定义两个指针分别表示长的和短的链表
    int dist = 0;
    // 判断哪个链表更长
    if (lena > lenb)
    {
        longList = LA->next;
        shortList = LB->next;
        dist = lena - lenb; // 计算长度差
    }
    else
    {
        longList = LB->next;
        shortList = LA->next;
        dist = lenb - lena; // 计算长度差
    }

    // 让长的链表先遍历若干节点
    while (dist--)
    {
        longList = longList->next;
    }

    // 同步遍历两个链表
    while (longList != NULL)
    {
        // 如果相等，表示找到了公共节点
        if (longList == shortList)
        {
            break;
        }
        else
        {
            longList = longList->next; // 移动到下一个节点
            shortList = shortList->next; // 移动到下一个节点
        }
    }

    // 打印公共节点后的数据
    while (longList)
    {
        cout << longList->data << '\t'; // 输出数据
        longList = longList->next; // 移动到下一个节点
    }
}

int main()
{
    LNode *p1 = new LNode; // 创建链表A的头节点

    LNode *q1 = new LNode; // 创建链表B的头节点
    LNode *q2 = new LNode; // 创建链表B的第二个节点
    LNode *q3 = new LNode; // 创建链表B的第三个节点

    // 创建公共节点
    LNode *m1 = new LNode;
    m1->data = 'm'; // 设置公共节点数据
    LNode *m2 = new LNode;
    m2->data = 'n'; // 设置公共节点数据

    m1->next = m2; // m1指向m2
    m2->next = NULL; // m2的next指向NULL
    p1->next = m1; // 链表A的next指向公共节点m1

    // 链表B的结构设置
    q1->next = q2; // q1指向q2
    q2->next = q3; // q2指向q3
    q3->next = m1; // q3指向公共节点m1

    // 查找并打印公共节点后的数据
    PublicNode(p1, q1);
}

（24）题目：用单链表保存 m 个整数，结点的结构为[data][link]，且ldatalsn(n为正整数),现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。

例如,若给定的单链表 head 如下：

解题思路：

>用空间换时间

>开辟辅助数组保存链表中的绝对值

实现代码：

#include <iostream>
#include <string.h>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;              // 节点数据
    struct LNode *next;    // 指向下一个节点的指针
} LNode, *LinkList;

// 头插法
void HeadInsert(LinkList &L)
{
    int val = '\0';
    // 读取输入，直到遇到换行符
    while (cin >> val)
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 更新头指针指向新节点

        if (cin.get() == '\n') // 如果读取到换行符，结束输入
        {
            break;
        }
    }
}

// 尾插法
void TailInsert(LinkList &L)
{
    int val = 0;
    LNode *r = L; // r指向链表的最后一个节点
    // 读取输入，直到遇到换行符
    while (cin >> val)
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 将当前尾节点的next指向新节点
        r = s;               // 更新r为新节点
        r->next = NULL;      // 新节点的next指向NULL

        if (cin.get() == '\n') // 如果读取到换行符，结束输入
        {
            break;
        }
    }
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // p指向链表的第一个节点
    while (p) // 遍历链表
    {
        cout << p->data << '\t'; // 输出当前节点数据
        p = p->next; // 移动到下一个节点
    }
    cout << endl; // 输出换行
}

// 删除链表中绝对值重复的节点
void DelValue(LinkList &L, int n)
{
    LNode *p, *r, *pre;   // 定义工作指针p、删除指针r和前驱指针pre
    int x = 0;            // 保存当前节点数据的绝对值
    int arr[n + 1] = {0}; // 定义辅助数组，用于记录绝对值是否出现过

    p = L->next; // p指向链表的第一个节点
    pre = L;     // pre指向头节点

    while (p) // 遍历链表
    {
        x = p->data > 0 ? p->data : -p->data; // 获取当前节点数据的绝对值

        // 如果绝对值没有出现过，则记录并继续
        if (arr[x] == 0)
        {
            arr[x] = 1; // 标记该绝对值已出现
            pre = p;    // 更新前驱指针为当前节点
            p = p->next; // 移动到下一个节点
        }
        // 如果绝对值已经出现过，则删除当前节点
        else
        {
            r = p->next; // 记录下一个节点
            pre->next = p->next; // 前驱节点的next跳过当前节点
            delete p; // 删除当前节点
            p = r; // 移动到下一个节点
        }
    }
}

int main()
{
    LinkList L = new LNode; // 创建链表的头节点
    TailInsert(L); // 调用尾插法插入数据
    Print(L); // 输出链表元素

    DelValue(L, 30); // 删除绝对值重复的节点
    Print(L); // 再次输出链表元素
}

（25）题目：设线性表L=(a,a,,a,, ,a2,a,a)采用带头结点单链表保存，链表中的结点定义如下：typedef struct nodeint data;struct node*next;}NODE;请设计一个空间复杂度为0(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L'=(a,a,,a2,a,-,a,,a-2,).

要求：

给出算法的基本设计思想。
根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
说明你所设计的算法的时间复杂度CSDN

解题思路：

关键点：

绝对值相等的节点：在删除时必须考虑节点的 data 值的绝对值，这与一般删除重复值问题不同。
保留首次出现的节点：对于绝对值相等的节点，保留首次出现的节点，而删除后续出现的绝对值相同的节点。

高效算法的思路：

要实现高效删除，可以使用一个哈希表来记录已经出现过的数值的绝对值。使用哈希表的原因是其查找和插入操作的时间复杂度为O(1)。这样我们可以在线性时间内（O(n)）遍历链表，并处理每个节点是否需要删除。

算法思路：

创建哈希表：用一个哈希表来存储已经访问过的节点的绝对值。
遍历链表：从链表的头节点开始，依次遍历每个节点：
- 如果当前节点的数据的绝对值已经在哈希表中存在，则删除该节点。
- 如果当前节点的数据的绝对值不在哈希表中，则将其绝对值加入哈希表，继续遍历下一个节点。
删除节点：如果发现节点需要删除，则调整前驱节点的 next 指针，跳过当前节点。

实现代码：

#include <iostream>
#include <string.h>
using namespace std;

// 定义链表节点结构体
typedef struct LNode
{
    int data;               // 节点数据
    struct LNode *next;    // 指向下一个节点的指针
} LNode, *LinkList;

// 头插法
void HeadInsert(LinkList &L)
{
    int val = '\0'; // 初始化输入值
    while (cin >> val) // 循环读取整数
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 将新节点插入链表头部

        // 如果输入回车，则结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}

// 尾插法
void TailInsert(LinkList &L)
{
    int val = 0;           // 初始化输入值
    LNode *r = L;         // r指向链表的尾部（初始为头节点）
    while (cin >> val) // 循环读取整数
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 当前尾节点的 next 指向新节点
        r = s;               // 更新 r 为新节点
        r->next = NULL;      // 新节点的 next 设置为 NULL

        // 如果输入回车，则结束输入
        if (cin.get() == '\n')
        {
            break;
        }
    }
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从链表第一个节点开始
    while (p)           // 当 p 不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}

// 变换链表
void ChangeList(LinkList &L)
{
    LNode *p, *q, *r, *s;
    p = q = L; // p 和 q 都指向头节点

    // 找到链表的末尾节点
    while (q->next)
    {
        p = p->next; // p 指向当前的最后一个节点
        q = q->next; // q 向前移动一位
        if (q->next != NULL)
        {
            q = q->next; // q 再向前移动一位，跳过一个节点
        }
    }
    q = p->next; // q 指向中间部分的第一个节点
    p->next = NULL; // 将后半部分的头节点的 next 设为 NULL

    // 反转后半部分链表
    while (q != NULL)
    {
        r = q->next; // 保存下一个节点
        q->next = p->next; // 将当前节点插入到 p 后面
        p->next = q; // 更新 p 的 next
        q = r; // 处理下一个节点
    }

    s = L->next; // 保存前半部分的头节点
    q = p->next; // q 指向反转后的链表
    p->next = NULL; // 将 p 的 next 设为 NULL，表示结束

    // 将后半部分插入到前半部分
    while (q != NULL)
    {
        r = q->next; // 保存下一个节点
        q->next = s->next; // 将后半部分节点插入到前半部分
        s->next = q; // 更新前半部分的 next
        s = q->next; // 移动前半部分的指针
        q = r; // 处理下一个节点
    }
}

int main()
{
    LinkList L = new LNode; // 创建链表的头节点
    TailInsert(L); // 调用尾插法插入节点

    ChangeList(L); // 调用变换链表的函数
    Print(L); // 输出变换后的链表
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构与算法