当前位置： 首页 > article >正文

【数据结构】链表应用1

article 2025/2/7 0:26:22

链表应用

  • 面试题 02.02.返回倒数第k个节点
    • 题目描述
    • 思路
    • 解题过程
    • 复杂度
  • 查找相同后缀
    • 题目描述
    • 解题思路
    • 完整代码：
  • 删除绝对值相等的节点
    • 题目描述
    • 解题思路
    • 代码

面试题 02.02.返回倒数第k个节点

题目描述

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意： 本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：
给定的 k 保证是有效的。

思路

使用快慢指针

解题过程

  • 初始化两个快慢指针，都指向head(注意不是head->nert，否则会报错说指向空指针)
  • 先让快指针走k步；再快慢指针同步走；直到快指针指向NULL；此时慢指针的数据就是期望数据。

复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k)
{
    if (head ==NULL)
        return 0;
    struct ListNode *fast = head;
    struct ListNode *slow = head;

    for (int i = 0; i < k; i ++)
    {
        if (fast ==NULL)
            return 0;
        fast = fast->next;
    }
    while (fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

作者：北国无红豆
链接：https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/solutions/3050388/kuai-man-zhi-zhen-jie-jue-dao-shu-di-kge-qdml/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

注意初始化的时候要写指向head，不能指向head->next，否则会不通过，报警告，说指向空指针

    struct ListNode *fast = head;
    struct ListNode *slow = head;

放一份完整的代码，这样写(初始化指向head->next)也能找到期望数据，这里不太理解

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}

/**
 * @Description:单链表 - 尾插法插入数据
 * @param {Node} *tail   尾节点
 * @param {ElemType} e   插入的数据
 * @return {*}           返回新的尾节点
 */
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

/**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

/**
 * @Description:单链表 - 删除指定位置的节点
 * @param {Node} *L 单链表的头节点
 * @param {int} pos 位置
 * @return {*}       返回1表示成功
 */
int DeletePosNode(Node *L, int pos)
{
    // 用来保存删除位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到删除节点的前驱节点
    while (i < pos - 1) // 遍历到删除位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("删除位置不合法\n");
            return 0;
        }
    }
    if (p->next == NULL) // 判断删除位置是否合法
    {
        printf("删除位置不合法\n");
        return 0;
    }
    Node *q = p->next; // 保存要删除的节点的地址
    p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
    free(q);           // 释放删除节点的内存

    return 1; // 返回1表示成功
}

int GetListLength(Node *L)
{
    int length = 0;
    Node *p = L; // 从头节点开始遍历,头节点算在内

    while (p != NULL)
    {
        p = p->next;
        length++;
    }
    return length;
}

void FreeList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放
    Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在
    while (p != NULL)
    {
        q = p->next; // 保存下一个节点的地址
        free(p);     // 释放当前节点的内存
        p = q;       // 移动到下一个节点
    }
    L->next = NULL; // 头节点的指针域为空
}

// 查找倒数第k个节点
int findNodeFS(Node *L, int k)
{
    Node *fast = L->next;
    Node *slow = L->next;

    for (int i = 0; i < k; i++)
    {
        fast = fast->next;
    }

    while (fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }

    printf("倒数第%d个节点值为：%d\n", k, slow->data);
    return 1;
}

int main()
{
    Node *list = InitList();
    Node *tail = GetTail(list);
    tail = InsertTail(tail, 10);
    tail = InsertTail(tail, 20);
    tail = InsertTail(tail, 30);
    tail = InsertTail(tail, 40);
    tail = InsertTail(tail, 50);
    tail = InsertTail(tail, 60);
    tail = InsertTail(tail, 70);
    TraverseList(list);
    findNodeFS(list, 3);

    return 0;
}

输出数据：

10 20 30 40 50 60 70
倒数第3个节点值为：50

请按任意键继续. . .

查找相同后缀

题目描述

【2012】假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。

在这里插入图片描述

设str1和str2分别指向两个单词所在单链表的头节点，链表节点结构为data | next，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图字符i所在节点的位置p）。要求：

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

解题思路

  1. 分别求出两个链表的长度m和n
  2. Fast指向较长的链表，先走m-n或者n-m步
  3. 同步移动指针，判断他们是否指向同一个节点

在这里插入图片描述

在这里插入图片描述

完整代码：

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}

// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{
    Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存
    node->data = e;                            // 节点的数据域为e
    node->next = NULL;                         // 节点的指针域为空
    return node;                               // 返回节点
}

/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%c", p->data); // 输出节点的数据域,这里是%c,因为ElemType是char类型
        p = p->next;           // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}

/**
 * @Description:单链表 - 尾插法插入数据
 * @param {Node} *tail   尾节点
 * @param {ElemType} e   插入的数据
 * @return {*}           返回新的尾节点
 */
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

/**
 * @Description:单链表 - 在链表尾部插入节点
 * @param {Node} *tail   链表尾部节点
 * @param {Node} *node   要插入的节点
 * @return {Node *}      插入节点后的链表尾部节点
 */
Node *InsertTailWithNode(Node *tail, Node *node)
{
    tail->next = node; // 尾节点的指针域指向要插入的节点
    node->next = NULL; // 要插入的节点的指针域为空
    return node;       // 返回新的尾节点
}

/**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

/**
 * @Description:单链表 - 删除指定位置的节点
 * @param {Node} *L 单链表的头节点
 * @param {int} pos 位置
 * @return {*}       返回1表示成功
 */
int DeletePosNode(Node *L, int pos)
{
    // 用来保存删除位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到删除节点的前驱节点
    while (i < pos - 1) // 遍历到删除位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("删除位置不合法\n");
            return 0;
        }
    }
    if (p->next == NULL) // 判断删除位置是否合法
    {
        printf("删除位置不合法\n");
        return 0;
    }
    Node *q = p->next; // 保存要删除的节点的地址
    p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
    free(q);           // 释放删除节点的内存

    return 1; // 返回1表示成功
}

int GetListLength(Node *L)
{
    int length = 0;
    Node *p = L; // 从头节点开始遍历,头节点算在内

    while (p != NULL)
    {
        p = p->next;
        length++;
    }
    return length;
}

void FreeList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放
    Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在
    while (p != NULL)
    {
        q = p->next; // 保存下一个节点的地址
        free(p);     // 释放当前节点的内存
        p = q;       // 移动到下一个节点
    }
    L->next = NULL; // 头节点的指针域为空
}

// 查找倒数第k个节点
int findNodeFS(Node *L, int k)
{
    Node *fast = L->next;
    Node *slow = L->next;

    for (int i = 0; i < k; i++)
    {
        fast = fast->next;
    }

    while (fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }

    printf("倒数第%d个节点值为：%d\n", k, slow->data);
    return 1;
}

// 查找两个节点共同后缀的起始位置
Node *findIntersectionNode(Node *headA, Node *headB)
{
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }

    Node *p = headA;
    int lenA = 0;
    int lenB = 0;

    // 遍历链表A，获取链表A的长度
    while (p != NULL)
    {
        p = p->next;
        lenA++;
    }
    // 遍历链表B，获取链表B的长度
    p = headB;
    while (p != NULL)
    {
        p = p->next;
        lenB++;
    }

    Node *fast; // 快指针
    Node *slow; // 慢指针
    int step;   // 两个单词之间数量的差值，可以用于快指针先走的步数
    if (lenA > lenB)
    {
        step = lenA - lenB;
        fast = headA;
        slow = headB;
    }
    else
    {
        step = lenB - lenA;
        fast = headB;
        slow = headA;
    }
    // 让快指针先走step步
    for (int i = 0; i < step; i++)
    {
        fast = fast->next;
    }
    // 快慢指针同步走，直到指向同一个节点退出循环
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

int main(int argc, char const *argv[])
{
    // 初始化链表
    Node *listA = InitList();
    Node *listB = InitList();
    // 获取尾节点
    Node *tailA = GetTail(listA);
    Node *tailB = GetTail(listB);

    // 尾插法插入数据 - A: load
    tailA = InsertTail(tailA, 'l');
    tailA = InsertTail(tailA, 'o');
    tailA = InsertTail(tailA, 'a');
    tailA = InsertTail(tailA, 'd');
    // 尾插法插入数据 - B: be
    tailB = InsertTail(tailB, 'b');
    tailB = InsertTail(tailB, 'e');

    Node *nodeI = InitListWithElem('i'); // 共享存储空间
    tailA = InsertTailWithNode(tailA, nodeI);
    tailB = InsertTailWithNode(tailB, nodeI);
    Node *nodeN = InitListWithElem('n');
    tailA = InsertTailWithNode(tailA, nodeN);
    tailB = InsertTailWithNode(tailB, nodeN);
    Node *nodeG = InitListWithElem('g');
    tailA = InsertTailWithNode(tailA, nodeG);
    tailB = InsertTailWithNode(tailB, nodeG);

    // 遍历链表A和链表B
    TraverseList(listA);
    TraverseList(listB);

    printf("%c\n", findIntersectionNode(listA, listB)->data);
    return 0;
}

输出：

loading
being
i

请按任意键继续. . .

注意：修改的代码有几处，

元素类型改成char

typedef char ElemType; // 定义元素类型

遍历输出字符，改成%c

void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%c", p->data); // 输出节点的数据域,这里是%c,因为ElemType是char类型
        p = p->next;           // 移动到下一个节点
    }
    printf("\n"); // 换行
}

新增函数 初始化节点（带节点数据域参数）

// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{
    Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存
    node->data = e;                            // 节点的数据域为e
    node->next = NULL;                         // 节点的指针域为空
    return node;                               // 返回节点
}

新增函数 - 在链表尾部插入节点

 /**
 * @Description:单链表 - 在链表尾部插入节点
 * @param {Node} *tail   链表尾部节点
 * @param {Node} *node   要插入的节点
 * @return {Node *}      插入节点后的链表尾部节点
 */
Node *InsertTailWithNode(Node *tail, Node *node)
{
    tail->next = node; // 尾节点的指针域指向要插入的节点
    node->next = NULL; // 要插入的节点的指针域为空
    return node;       // 返回新的尾节点
}

然后才是任务函数 - 查找两个节点共同后缀的起始位置


// 查找两个节点共同后缀的起始位置
Node *findIntersectionNode(Node *headA, Node *headB)
{
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }

    Node *p = headA;
    int lenA = 0;
    int lenB = 0;

    // 遍历链表A，获取链表A的长度
    while (p != NULL)
    {
        p = p->next;
        lenA++;
    }
    // 遍历链表B，获取链表B的长度
    p = headB;
    while (p != NULL)
    {
        p = p->next;
        lenB++;
    }

    Node *fast; // 快指针
    Node *slow; // 慢指针
    int step;   // 两个单词之间数量的差值，可以用于快指针先走的步数
    if (lenA > lenB)
    {
        step = lenA - lenB;
        fast = headA;
        slow = headB;
    }
    else
    {
        step = lenB - lenA;
        fast = headB;
        slow = headA;
    }
    // 让快指针先走step步
    for (int i = 0; i < step; i++)
    {
        fast = fast->next;
    }
    // 快慢指针同步走，直到指向同一个节点退出循环
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

最后在main函数里创造being和loading的字符条件，调用findIntersectionNode函数输出即可。

删除绝对值相等的节点

题目描述

在这里插入图片描述

解题思路

用空间换时间，用一个数组来存储已经出现过的绝对值，如果绝对值已经出现过，就删除该节点
在堆内存（指针）中分配一个数组，用来存储已经出现过的绝对值
当前链表最多有n个节点（因为有n个整数）

在这里插入图片描述

代码

/**
 * @description: 用单链表保存n个整数，节点的结构为[data][link]，且|data|<=n(n为正整数)。
 * 现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的节点，
 * 仅保留第一次出现的节点而删除其余绝对值相等的节点。
 * 例如，给定单链表head如下：head-> 21 -> -15 -> 15 -> -7 -> 15
 * 则删除后的链表head为：head-> 21 -> -15 -> -7
 *
 * 思路：用空间换时间，用一个数组来存储已经出现过的绝对值，如果绝对值已经出现过，就删除该节点
 */

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}

// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{
    Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存
    node->data = e;                            // 节点的数据域为e
    node->next = NULL;                         // 节点的指针域为空
    return node;                               // 返回节点
}

/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域,这里是%d,因为ElemType是int类型
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}

/**
 * @Description:单链表 - 尾插法插入数据
 * @param {Node} *tail   尾节点
 * @param {ElemType} e   插入的数据
 * @return {*}           返回新的尾节点
 */
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

/**
 * @Description:单链表 - 在链表尾部插入节点
 * @param {Node} *tail   链表尾部节点
 * @param {Node} *node   要插入的节点
 * @return {Node *}      插入节点后的链表尾部节点
 */
Node *InsertTailWithNode(Node *tail, Node *node)
{
    tail->next = node; // 尾节点的指针域指向要插入的节点
    node->next = NULL; // 要插入的节点的指针域为空
    return node;       // 返回新的尾节点
}

/**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

/**
 * @Description:单链表 - 删除指定位置的节点
 * @param {Node} *L 单链表的头节点
 * @param {int} pos 位置
 * @return {*}       返回1表示成功
 */
int DeletePosNode(Node *L, int pos)
{
    // 用来保存删除位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到删除节点的前驱节点
    while (i < pos - 1) // 遍历到删除位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("删除位置不合法\n");
            return 0;
        }
    }
    if (p->next == NULL) // 判断删除位置是否合法
    {
        printf("删除位置不合法\n");
        return 0;
    }
    Node *q = p->next; // 保存要删除的节点的地址
    p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
    free(q);           // 释放删除节点的内存

    return 1; // 返回1表示成功
}

int GetListLength(Node *L)
{
    int length = 0;
    Node *p = L; // 从头节点开始遍历,头节点算在内

    while (p != NULL)
    {
        p = p->next;
        length++;
    }
    return length;
}

void FreeList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放
    Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在
    while (p != NULL)
    {
        q = p->next; // 保存下一个节点的地址
        free(p);     // 释放当前节点的内存
        p = q;       // 移动到下一个节点
    }
    L->next = NULL; // 头节点的指针域为空
}

// 查找倒数第k个节点
int findNodeFS(Node *L, int k)
{
    Node *fast = L->next;
    Node *slow = L->next;

    for (int i = 0; i < k; i++)
    {
        fast = fast->next;
    }

    while (fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }

    printf("倒数第%d个节点值为：%d\n", k, slow->data);
    return 1;
}

// 查找两个节点共同后缀的起始位置
Node *findIntersectionNode(Node *headA, Node *headB)
{
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }

    Node *p = headA;
    int lenA = 0;
    int lenB = 0;

    // 遍历链表A，获取链表A的长度
    while (p != NULL)
    {
        p = p->next;
        lenA++;
    }
    // 遍历链表B，获取链表B的长度
    p = headB;
    while (p != NULL)
    {
        p = p->next;
        lenB++;
    }

    Node *fast; // 快指针
    Node *slow; // 慢指针
    int step;   // 两个单词之间数量的差值，可以用于快指针先走的步数
    if (lenA > lenB)
    {
        step = lenA - lenB;
        fast = headA;
        slow = headB;
    }
    else
    {
        step = lenB - lenA;
        fast = headB;
        slow = headA;
    }
    // 让快指针先走step步
    for (int i = 0; i < step; i++)
    {
        fast = fast->next;
    }
    // 快慢指针同步走，直到指向同一个节点退出循环
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

// 函数：RemoveEqualNodes
// 功能：删除链表中与给定值相等的节点
// 参数：Node *L：链表头指针，int n：链表的长度
// 返回值：无
void RemoveEqualNodes(Node *L, int n)
{
    // TODO: 实现删除链表中与给定值相等的节点的功能
    Node *p = L;                                   // 定义一个指针p，指向链表的头节点
    int index;                                     // 定义一个变量index，作为数组下标使用
    int *q = (int *)malloc(sizeof(int) * (n + 1)); // 在堆内存中分配一个数组，用来存储已经出现过的绝对值

    /* 遍历数组，初始化为0 */
    for (int i = 0; i < n + 1; i++)
    {
        *(q + i) = 0; // 初始化为0，表示没有出现过这个绝对值
    }

    while (p->next != NULL)
    {
        // 获取绝对值
        index = abs(p->next->data); // 计算当前节点的绝对值，作为数组下标使用

        if (*(q + index) == 0) // 如果这个绝对值没有出现过
        {
            *(q + index) = 1; // 标记为已经出现过
            p = p->next;      // 移动到下一个节点
        }
        else // 如果这个绝对值已经出现过,删除当前节点
        {
            Node *tempNode = p->next; // 保存要删除的节点的地址
            p->next = tempNode->next; // 删除当前节点
            free(tempNode);           // 释放当前节点的内存
        }
    }
    free(q); // 释放数组的内存
}

int main()
{
    // 初始化链表
    Node *list = InitList();

    // 获取尾节点
    Node *tail = GetTail(list);

    tail = InsertTail(tail, 21);
    tail = InsertTail(tail, 22);
    tail = InsertTail(tail, 23);
    tail = InsertTail(tail, -21);
    tail = InsertTail(tail, 10);
    tail = InsertTail(tail, -22);
    tail = InsertTail(tail, -23);

    TraverseList(list); // 遍历链表

    // 删除绝对值相等的节点
    RemoveEqualNodes(list, 23); // 传入链表头指针和 n个整数的n值
    TraverseList(list);         // 遍历链表
    return 0;
}

输出正确

在这里插入图片描述

在这里插入图片描述


http://www.kler.cn/a/534358.html

相关文章：

  • DeepSeek-V3：开源多模态大模型的突破与未来
  • 算法：线性同余法(LCG,Linear Congruential Generator)
  • 360手机刷机 360手机解Bootloader 360手机ROOT
  • 【学Rust写CAD】3 绝对坐标系详解
  • doris:临时分区
  • “AI智能分析综合管理系统：企业管理的智慧中枢
  • java中反射（Reflection）的4个作用
  • [Python人工智能] 四十九.PyTorch入门 (4)利用基础模块构建神经网络并实现分类预测
  • 我的鸿蒙学习之旅：探索万物互联的新宇宙
  • 产品经理的人工智能课 02 - 自然语言处理
  • 穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞黄金矿工
  • 移动机器人规划控制入门与实践：基于navigation2 学习笔记（一）
  • 【Uniapp-Vue3】从uniCloud中获取数据
  • Vue全流程--Vue2组件的理解第二部分
  • Docker深度解析：Docker Compose
  • 巧用 DeepSeek，让 Excel 数据处理更高效
  • Springboot项目编写测试单元步骤
  • 北大AGI与具身智能评估新范式！Tong测试：基于动态具身物理和社会互动的评估标准
  • 【go语言】protobuf 和 grpc
  • mixin
  • STM32 串口收发数据包
  • 基于springboot+vue的青少年心理健康教育网站的设计与实现
  • Qt跨屏窗口的一个Bug及解决方案
  • FRP通过公网IP实现内网穿透
  • 日期选择控件，时间跨度最大一年。
  • springboot停车场管理系统设计与实现