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

嵌入式软件数据结构（一）链表知识点专栏 附源码 附原理

article 2025/2/27 2:29:23

嵌入式软件数据结构（一）链表知识点专栏 附源码 附原理  前言：

首先我们要知道什么是链表？

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）链表的入口节点称为链表的头结点也就是head。

链表就像是一个由一串小纸条组成的链条，每个纸条上有两部分内容：一部分是写的数字或者信息（就是数据），另一部分是指向下一个纸条的箭头。最后一个纸条上没有箭头，说明它是链条的终点。你可以从第一个纸条（头结点）开始，按照箭头一个一个地找到下去。

每次想在链表中加入新纸条时，你只需要把新纸条和前一个纸条用箭头连接起来；如果要拿掉一个纸条，只需要把前面那个纸条的箭头指向后面那个纸条就行，不需要移动其他纸条。

链表的好处是插入和删除纸条很方便，但如果你想要快速找到某个纸条，就得从头开始一条条地找。

这样说，链表是不是更直观了一些？

如图所示：

链表的类型

接下来说一下链表的几种类型:

单链表

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示：

 

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的存储方式

了解完链表的类型，再来说一说链表在内存中的存储方式。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示：

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的操作

删除D节点，如图所示：

 

只要将C节点的next指针 指向E节点就可以了。

那有同学说了，D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。

是这样的，所以在C++里最好是再手动释放这个D节点，释放这块内存。

其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

添加节点

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

再把链表的特性和数组的特性进行一个对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

删除单链表的重复节点

面试题 02.01. 移除重复节点 - 力扣（LeetCode）

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeDuplicateNodes(struct ListNode* head) {
   if (head == NULL) return NULL;
    bool hash[20001] = {false}; // 假设节点值的范围在0到20000之间
    struct ListNode dummy = {0, head};
    struct ListNode *prev = &dummy;
    struct ListNode *current = head;
    while (current != NULL) {
        if (hash[current->val]) {
            // 删除当前节点
            prev->next = current->next;
            free(current);
            current = prev->next;
        } else {
            hash[current->val] = true;
            prev = current;
            current = current->next;
        }
    }
    return head;
}

 

如何找出链表的倒数第K个元素？

LCR 140. 训练计划 II - 力扣（LeetCode）

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    if (head == NULL || cnt <= 0) {
        return NULL;
    }

    struct ListNode *fast = head, *slow = head;
    
    // Move fast pointer cnt steps ahead
    for (int i = 0; i < cnt; i++) {
        if (fast == NULL) return NULL;  // If cnt is greater than the length of the list
        fast = fast->next;
    }

    // Move both fast and slow pointers until fast reaches the end
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    // Now slow points to the cnt-th node from the end
    return slow;
}

如何找出链表的中间节点

876. 链表的中间结点 - 力扣（LeetCode）

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode *fast = head, *slow = head;
    
    // 快慢指针，fast 每次移动 2 步，slow 每次移动 1 步
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;  // fast 移动两步
        slow = slow->next;        // slow 移动一步
    }
    
    // 当 fast 指针到达链表末尾时，slow 指针就指向中间节点
    return slow;
}

反转链表

LCR 141. 训练计划 III - 力扣（LeetCode）

给定一个头节点为 head 的单链表用于记录一系列核心肌群训练编号，请将该系列训练编号 倒序 记录于链表并返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* trainningPlan(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next = NULL;
    
    // 遍历链表并反转指针
    while (curr != NULL) {
        next = curr->next;    // 保存当前节点的下一个节点
        curr->next = prev;    // 将当前节点的指针反向
        prev = curr;          // prev 前移，指向当前节点
        curr = next;          // curr 前移，指向下一个节点
    }
    
    // 返回新的头节点
    return prev;
}

环形链表

141. 环形链表 - 力扣（LeetCode）

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if (head == NULL) return false;

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

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;           // 慢指针每次走一步
        fast = fast->next->next;     // 快指针每次走两步

        // 如果快慢指针相遇，说明有环
        if (slow == fast) {
            return true;
        }
    }

    // 如果 fast 指针到达链表的末尾，说明没有环
    return false;
}

单链表相交，如何求交点？

面试题 02.07. 链表相交 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    
    struct ListNode *pA = headA;
    struct ListNode *pB = headB;

    // 遍历两个链表，指针 pA 和 pB 将同时遍历相同的长度
    while (pA != pB) {
        // 如果 pA 到达链表末尾，则跳转到链表 B 的头
        pA = (pA == NULL) ? headB : pA->next;
        // 如果 pB 到达链表末尾，则跳转到链表 A 的头
        pB = (pB == NULL) ? headA : pB->next;
    }
    
    // 当 pA 和 pB 相遇时，返回交点（可能是 NULL，表示没有交点）
    return pA;
}

回文链表

234. 回文链表 - 力扣（LeetCode）

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
// 反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 判断链表是否为回文
bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return true;  // 空链表或只有一个节点的链表是回文的
    }

    // 快慢指针找到链表中间节点
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 反转后半部分链表
    struct ListNode* secondHalf = reverseList(slow);
    struct ListNode* firstHalf = head;

    // 比较前半部分和反转后的后半部分
    while (secondHalf != NULL) {
        if (firstHalf->val != secondHalf->val) {
            return false;  // 如果不相等，说明不是回文链表
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }

    return true;  // 如果所有节点相等，则是回文链表
}

移除重复节点

面试题 02.01. 移除重复节点 - 力扣（LeetCode）

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeDuplicateNodes(struct ListNode* head) {
   if (head == NULL) return NULL;
    bool hash[20001] = {false}; // 假设节点值的范围在0到20000之间
    struct ListNode dummy = {0, head};
    struct ListNode *prev = &dummy;
    struct ListNode *current = head;
    while (current != NULL) {
        if (hash[current->val]) {
            // 删除当前节点
            prev->next = current->next;
            free(current);
            current = prev->next;
        } else {
            hash[current->val] = true;
            prev = current;
            current = current->next;
        }
    }
    return head;
}

用普通算法实现两个有序链表合并

21. 合并两个有序链表 - 力扣（LeetCode）

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 如果 l1 为 NULL，直接返回 l2
    if (l1 == NULL) return l2;
    // 如果 l2 为 NULL，直接返回 l1
    if (l2 == NULL) return l1;

    // 比较 l1 和 l2 当前节点的值，选择较小的节点
    if (l1->val < l2->val) {
        // 如果 l1 的值较小，递归合并 l1 的下一个节点和 l2
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        // 如果 l2 的值较小，递归合并 l1 和 l2 的下一个节点
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}


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

相关文章：

  • Pycharm-Version: 2024.3.3导入conda环境
  • C# 根据Ollama+DeepSeekR1开发本地AI辅助办公助手
  • Node.js 中 fs 模块的高级用法
  • Python入门 — 类
  • SQL: DDL,DML,DCL,DTL,TCL,
  • 如何使用VMware创建虚拟机
  • 解释 React 中的 JSX 语法，如何编译成 React.createElement的过程？
  • Vue.js 测试 Vuex 和 Vue Router
  • 计算机网络模型-TCP/IP协议簇
  • 创建型模式 - 原型模式 (Prototype Pattern)
  • 2025面试Go真题第一场
  • 游戏引擎学习第123天
  • MyBatis简明教程
  • es-head（es库-谷歌浏览器插件）
  • Git系列之Git Reset
  • 量子计算如何改变加密技术：颠覆与变革的前沿
  • MLops：可解释深度神经网络训练平台Neural Designer ®
  • HBase与传统数据库的区别：为什么选择它来处理大数据？
  • MySQL 根据条件多值更新
  • 中兴B863AV3.2-T／B863AV3.1-T2／B863AV3.1-T2K_电信高安_S905L3A-B_安卓9.0_线刷固件包