【数据结构】链表应用1

面试题 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;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->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;                            // 在新节点的数据域存入数据etail->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;                            // 在新节点的数据域存入数据enewnode->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;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存node->data = e;                            // 节点的数据域为enode->next = NULL;                         // 节点的指针域为空return node;                               // 返回节点
}/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->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;                            // 在新节点的数据域存入数据etail->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;                            // 在新节点的数据域存入数据enewnode->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: loadtailA = InsertTail(tailA, 'l');tailA = InsertTail(tailA, 'o');tailA = InsertTail(tailA, 'a');tailA = InsertTail(tailA, 'd');// 尾插法插入数据 - B: betailB = 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和链表BTraverseList(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;                            // 节点的数据域为enode->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;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存node->data = e;                            // 节点的数据域为enode->next = NULL;                         // 节点的指针域为空return node;                               // 返回节点
}/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->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;                            // 在新节点的数据域存入数据etail->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;                            // 在新节点的数据域存入数据enewnode->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;
}

输出正确

---