【数据结构】链表应用1

链表应用

  • 面试题 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. 分别求出两个链表的长度mn
  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;
}

输出正确

在这里插入图片描述


在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/966471.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【JVM详解一】类加载过程与内存区域划分

一、简介 1.1 概述 JVM是Java Virtual Machine&#xff08;Java虚拟机&#xff09;的缩写&#xff0c;是通过在实际的计算机上仿真模拟各种计算机功能来实现的。由一套字节码指令集、一组寄存器、一个栈、一个垃圾回收堆和一个存储方法域等组成。JVM屏蔽了与操作系统平台相关…

基于STM32设计的仓库环境监测与预警系统

目录 项目开发背景设计实现的功能项目硬件模块组成设计思路系统功能总结使用的模块的技术详情介绍总结 1. 项目开发背景 随着工业化和现代化的进程&#xff0c;尤其是在制造业、食品业、医药业等行业&#xff0c;仓库环境的监控和管理成为了至关重要的一环。尤其是在存储易腐…

“可通过HTTP获取远端WWW服务信息”漏洞修复

环境说明&#xff1a;①操作系统&#xff1a;windows server&#xff1b;②nginx&#xff1a;1.27.1。 1.漏洞说明 “可通过HTTP获取远端WWW服务信息”。 修复前&#xff0c;在“响应标头”能看到Server信息&#xff0c;如下图所示&#xff1a; 修复后&#xff0c;“响应标头…

创建一个javaWeb Project

文章目录 前言一、eclipse创建web工程二、web.xmlservlet.xml< mvc:annotation-driven/ > Spring MVC 驱动< context:component - scan >&#xff1a;扫描< bean > ... < /bean >< import > config/beans.xml beans.xmlmybatis.xml 前言 javaWe…

aspectFill(填充目标区域的同时保持图像的原有宽高比 (aspect ratio)图像不会被拉伸或压缩变形

“aspectFill” 是一个常用于图像和视频处理的术语&#xff0c;尤其是在用户界面 (UI) 设计和图形编程领域。它描述的是一种图像缩放或调整大小的方式&#xff0c;旨在填充目标区域的同时保持图像的原有宽高比 (aspect ratio)。 更详细的解释: Aspect Ratio (宽高比): 指的是图…

界址点成果表批量生成(新增.docx格式)-附工具下载链接

界址点编号工具20250208更新&#xff08;成果表新增.docx格式&#xff09;。 【工具简介】工具可根据面图层&#xff0c;西北角顺时针批量生成界址点&#xff0c;可以设置角度、距离参数&#xff0c;来减少生成界址点的数量&#xff08;不用全部节点生成界址点&#xff09;。生…

《redis缓存淘汰机制》

【redis缓存淘汰机制导读】redis作为一款内存型数据库&#xff0c;其设计的初衷就是为了给广大业务层提供高效的数据读、写能力&#xff0c;因为访问内存的速度肯定是要比直接访问磁盘的速度快几个数量级&#xff0c;假设业务方所有数据读、写请求全部都转发到后台的数据库&…

AWK系统学习指南:从文本处理到数据分析的终极武器 介绍

目录 一、AWK核心设计哲学解析 1.1 记录与字段的原子模型 1.2 模式-动作范式 二、AWK编程语言深度解析 2.1 控制结构 说明&#xff1a; 2.2 关联数组 代码说明&#xff1a; 示例输入和输出&#xff1a; 注意事项&#xff1a; 2.3 内置函数库 三、高级应用技巧 3.1…

深入解析AI技术原理

序言 在当今数字化时代,人工智能(AI)已经成为科技领域最炙手可热的话题之一。从智能家居到自动驾驶汽车,从医疗诊断到金融风险预测,AI的应用无处不在。然而,对于许多人来说,AI背后的技术原理仍然充满了神秘色彩。本文将深入探讨AI的核心技术原理,从基础理论到前…

计算机组成原理(3)

计算机组成原理&#xff08;3&#xff09; 存储器层次结构存储器概述存储器分类存储器性能指标 半导体随机存储SRAM和DRAM 存储器层次结构 主存-辅存&#xff1a;实现了虚拟存储系统&#xff0c;解决了主存容量不足的问题&#xff1b; Cache-主存&#xff1a;解决了主存于CPU速…

计算机网络-SSH基本原理

最近年底都在忙&#xff0c;然后这两天好点抽空更新一下。前面基本把常见的VPN都学习了一遍&#xff0c;后面的内容应该又继续深入一点。 一、SSH简介 SSH&#xff08;Secure Shell&#xff0c;安全外壳协议&#xff09;是一种用于在不安全网络上进行安全远程登录和实现其他安…

【理论知识】 2D 卷积、3D 卷积与 3D 池化

摘要 卷积神经网络&#xff08;Convolutional Neural Networks, CNNs&#xff09;在计算机视觉、视频处理和医学影像分析等领域取得了显著的成功。卷积操作作为CNN的核心&#xff0c;主要包括二维卷积&#xff08;2D Convolution&#xff09;、三维卷积&#xff08;3D Convolu…

apisix网关ip-restriction插件使用说明

ip-restriction插件可以在网关层进行客户端请求ip拦截。 当然了&#xff0c;一般不推荐使用该方法&#xff0c;专业的事专业工具做。建议有条件&#xff0c;还是上防火墙或者waf来做。 官方文档&#xff1a;ip-restriction | Apache APISIX -- Cloud-Native API Gateway whit…

uniapp 编译生成鸿蒙正式app步骤

1&#xff0c;在最新版本DevEco-Studio工具新建一个空项目并生成p12和csr文件&#xff08;构建-生成私钥和证书请求文件&#xff09; 2&#xff0c;华为开发者平台 根据上面生成的csr文件新增cer和p7b文件&#xff0c;分发布和测试 3&#xff0c;在最新版本DevEco-Studio工具 文…

在亚马逊云科技上云原生部署DeepSeek-R1模型(下)

在本系列的上篇中&#xff0c;我们介绍了如何通过Amazon Bedrock部署并测试使用了DeepSeek模型。在接下来的下篇中小李哥将继续介绍&#xff0c;如何利用亚马逊的AI模型训练平台SageMaker AI中的&#xff0c;Amazon Sagemaker JumpStart通过脚本轻松一键式部署DeepSeek预训练模…

A new release of pip is available: 24.2 -> 25.0

您可以使用官方提供的 get-pip.py 脚本来安装或升级pip。 1&#xff0c;下载 get-pip.py 脚本&#xff1a; curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py 2&#xff0c;运行脚本以安装或升级pip&#xff1a; python get-pip.py 3&#xff0c;实际运行效果

使用WebUI访问本地Deepseek(Ollama集成Open WebUI)

在《deepseek本地部署和使用&#xff08;Linux虚拟机&#xff09;》中&#xff0c;我们使用Ollama部署了Deepseek-r1&#xff0c;但是只能通过命令行方式交互&#xff0c;默认Ollama启动后&#xff0c;会启动一个监听到127.0.0.1&#xff0c;用以接收POST 请求&#xff0c;服务…

[NKU]C++安装环境 VScode

bilibili安装教程 vscode 关于C/C的环境配置全站最简单易懂&#xff01;&#xff01;大学生及初学初学C/C进&#xff01;&#xff01;&#xff01;_哔哩哔哩_bilibili 1安装vscode和插件 汉化插件 ​ 2安装插件 2.1 C/C 2.2 C/C Compile run ​ 2.3 better C Syntax ​ 查看已…

DeepSeek图解10页PDF

以前一直在关注国内外的一些AI工具&#xff0c;包括文本型、图像类的一些AI实践&#xff0c;最近DeepSeek突然爆火&#xff0c;从互联网收集一些资料与大家一起分享学习。 本章节分享的文件为网上流传的DeepSeek图解10页PDF&#xff0c;免费附件链接给出。 1 本地 1 本地部…

如何将Excel的表格存为图片?

emmm&#xff0c;不知道题主具体的应用场景是什么&#xff0c;就分享几个我一般会用到的场景下奖excel表格保存为图片的技巧吧&#xff01; 先来个总结&#xff1a; 方法 适用场景 画质 操作难度 截图&#xff08;WinShiftS&#xff09; 快速保存表格&#xff0c;方便粘贴…