链表应用
- 面试题 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）。要求：
- 描述算法的基本设计思想；
- 根据设计思想，采用c/C++/Java语言描述，关键之处给出注释
- 说明你所设计算法的时间复杂度
解题思路
- 分别求出两个链表的长度
m和n - Fast指向较长的链表，先走
m-n或者n-m步 - 同步移动指针，判断他们是否指向同一个节点
完整代码：
#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;
}
输出正确
![[NKU]C++安装环境 VScode](https://i-blog.csdnimg.cn/direct/d1ae20f4c2cb49108fd0ef87a1836612.png)
