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

2.单链表练习

news 2025/7/20 2:24:03

1. 链表的基本概念

链表（Linked List）是一种常见的数据结构，用于存储一系列元素，这些元素可以是任意类型的数据。链表中的每个元素被称为节点（Node），每个节点包含两部分：一个存储数据的值（或称为数据域），以及一个指向下一个节点的引用（或称为指针或链接）。

链表与数组相比，具有一些优势和不同之处：

  1. 动态性： 链表的大小可以在运行时动态地改变，而数组的大小通常是静态的。

  2. 插入和删除： 在链表中插入或删除元素相对容易，只需修改节点的引用，不需要像数组一样移动大量元素。

  3. 空间利用： 链表可以有效地利用内存，因为每个节点只需存储自身的值和下一个节点的引用，而数组可能需要一块连续的内存空间。

链表有几种常见的类型，其中最常见的是单向链表和双向链表：

  1. 单向链表（Singly Linked List）： 每个节点包含一个数据域和一个指向下一个节点的引用。链表的首节点称为头节点，链表的尾节点的下一个节点引用为空。

  2. 双向链表（Doubly Linked List）： 每个节点包含一个数据域和两个引用，分别指向前一个节点和后一个节点。这使得在链表中可以双向遍历。

基本操作：

  1. 插入操作： 插入节点涉及创建一个新的节点，并将其插入到合适的位置。对于单向链表，需要修改前一个节点的引用，对于双向链表，还需要修改后一个节点的前向引用。

  2. 删除操作： 删除节点涉及将待删除节点的前一个节点的引用指向待删除节点的下一个节点。同样，对于双向链表，还需要修改后一个节点的前向引用。

  3. 搜索操作： 从头节点开始，按顺序遍历链表，查找特定值的节点。

  4. 遍历操作： 从头节点开始，按顺序访问链表的每个节点，执行所需的操作。

链表在许多编程场景中都有用途，例如实现栈、队列、缓存等数据结构，也常用于解决某些特定的问题，如链表反转、寻找中间节点等。然而，需要注意链表的操作可能比数组稍微复杂，因为需要更多的指针操作。

2. 题目中的结构体

struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* next;是单链表特性，除了储存value以外还都储存了next，指向下一个节点的指针。

这段代码定义了一个名为 ListNode 的结构体，用于表示链表中的节点。这个结构体有三个不同的构造函数，以便于创建节点对象：

  1. 默认构造函数：
ListNode() : val(0), next(nullptr) {}

这个构造函数会创建一个值为0、下一个节点为空的链表节点。

  1. 带有一个整数参数的构造函数：
ListNode(int x) : val(x), next(nullptr) {}

这个构造函数会创建一个具有给定整数值 x、下一个节点为空的链表节点。

  1. 带有两个参数的构造函数：
ListNode(int x, ListNode* next) : val(x), next(next) {}

这个构造函数会创建一个具有给定整数值 x 和指向下一个节点的指针 next 的链表节点。

在这个结构体中，val 成员变量用于存储节点的值，而 next 成员变量是一个指向下一个节点的指针。这样，我们就可以通过创建多个 ListNode 对象，并使用 next 指针将它们链接在一起，从而形成一个链表。

这个结构体的定义允许我们在链表操作中方便地创建和操作节点，以实现链表的常见操作，如插入、删除和遍历。

2. 移除链表元素

2.1 以案例来学习链表，普通的删除方法

复习指针

1. delete ptr不是删除指针, 而是释放指针指向的内存

这里因为tmp和head都指向了同一内存空间，所以delete tmp就是释放之前的head, 因为我们要对head进行一个变动

        while (head != NULL && head->val == val) { // 注意这里不是ifListNode* tmp = head;head = head->next;delete tmp;}

2. 比较容易的错误写法

在删除非头结点的时候容易犯这个错误, 因为是链表，写的时候就很容易参照链表的delete函数的写法，就是直接给一个tmp, 然后cur->next, 然后就直接删除，其实这样是不对的，因为链表删掉了中间节点还要考虑前后的加在一起

        // 删除非头结点的节点ListNode *cur = head; // 当前指针是headwhile (cur != NULL){if (cur->val == val){ListNode* tmp = cur; // tmp, head指向同一内存空间cur = cur->next; // 头结点指针指向原来链表的第二个节点delete tmp;}

#include <iostream>struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 删除头节点，同时也判断新的头结点是否需要删除while (head != NULL && head->val == val){ListNode *tmp = head;   // 这里让tmp指向需要被移除头结点同一地址head = head->next;      // 这里头结点的指针指向下一个节点delete tmp;             // 移除tmp, 同样也释放掉需要操作头结点的指针}// 删除非头结点的节点，这里不只是简单的删除，还要考虑把前一个后一个链接起来/*ex: 1->2->3->2->5, 处理2, 因为这里处理的是非头节点，在1位置链接3处理2，在3链接5处理2如果遍历的时候在2处理2，还要写一个prev指针如果5要处理，就在前一个地方(2)处理，5的next是nullptr, (2)链接5就行了*/ListNode *cur = head; // 这里已经考虑完了头结点, 所以这个头结点不用操作while (cur != NULL && cur->next != NULL){ // 遍历链表的基本手法if (cur->next->val == val){    ListNode *tmp = cur->next;cur->next = cur->next->next;delete tmp;}else {cur = cur->next;}}return head;}
};// 辅助函数：打印链表
void printList(ListNode* head) {ListNode* current = head;while (current != nullptr) {std::cout << current->val << " ";current = current->next;}std::cout << std::endl;
}// 这个地方跟上面删除非头结点最大的区别就是不用维护这个代码
void deleteList(ListNode* head) {ListNode* current = head;while (current != nullptr) {ListNode* tmp = current;current = current->next;delete tmp;}
}int main() {Solution solution;// 示例 1ListNode* head1 = new ListNode(1);head1->next = new ListNode(2);head1->next->next = new ListNode(6);head1->next->next->next = new ListNode(3);head1->next->next->next->next = new ListNode(4);head1->next->next->next->next->next = new ListNode(5);head1->next->next->next->next->next->next = new ListNode(6);int val1 = 6;ListNode* newHead1 = solution.removeElements(head1, val1);std::cout << "Case 1: ";printList(newHead1);// 示例 2ListNode* head2 = nullptr;int val2 = 1;ListNode* newHead2 = solution.removeElements(head2, val2);std::cout << "Case 2: ";printList(newHead2);// 示例 3ListNode* head3 = new ListNode(7);ListNode* current3 = head3;for (int val : {7, 7, 7}){current3->next = new ListNode(val);current3 = current3->next;}std::cout << "Oringin case 3: ";printList(head3);int val3 = 7;ListNode* newHead3 = solution.removeElements(head3, val3);std::cout << "Case 3: ";printList(newHead3);// 释放节点内存deleteList(newHead1);deleteList(newHead2);deleteList(newHead3);return 0;
}

2.2 虚拟头结点写法

这样就只用考虑处理非头结点的情况就好了, 注意这里实例化了之后要用引用，这里也是复习一下实例化和在堆上生成内存返回指针，下面有两种写法

栈上的内存（Stack）：当你创建一个局部变量或对象（例如ListNode dummy(0);）时，这个对象是在栈上分配内存的。这些对象的生命周期是确定的，当它们所在的作用域结束时，它们会自动被销毁，内存会被释放。

堆上的内存（Heap）：当你使用new关键字（例如ListNode* dummy = new ListNode(0);）时，对象是在堆上分配内存的。这些对象的生命周期是不确定的，你需要显式地使用delete来释放内存。

使用指针的一个主要优点是，它允许你在运行时动态地创建和销毁对象。这给了你更大的灵活性，但代价是你需要更仔细地管理内存。

实例化虚拟头节点

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode dummy(0);dummy.next = head;// 处理非头节点ListNode *cur = &dummy; // 这里已经考虑完了头结点, 所以这个头结点不用操作while (cur != NULL && cur->next != NULL){ // 遍历链表的基本手法if (cur->next->val == val){    ListNode *tmp = cur->next;cur->next = cur->next->next;delete tmp;}else {cur = cur->next;}}return dummy.next;}
};

指针虚拟头结点

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode *dummy = new ListNode(999);// 处理非头节点ListNode *cur = dummy; // 这里已经考虑完了头结点, 所以这个头结点不用操作while (cur != NULL && cur->next != NULL){ // 遍历链表的基本手法if (cur->next->val == val){    ListNode *tmp = cur->next;cur->next = cur->next->next;delete tmp;}else {cur = cur->next;}}return dummy->next;}
};

3. 设计一个链表

通过完整的设计一个链表理解链表是怎么遍历的，新的节点怎么在各个地方链接起来

#include <iostream>class MyLinkedList {
public:struct ListNode   // 先创建节点的结构体, val, next, 以及ListNode的构造函数{int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}};private:ListNode *head;    // 指向头结点的指针int size;          // 链表的尺寸public:MyLinkedList() {head = NULL;size = 0;}int get(int index) {// 这个就是取出索引的值if (index < 0 || index >= size)return -1;ListNode *cur = head;for (int i = 0; i < index; i++){cur = cur->next;}return cur->val;}void addAtHead(int val) {/*1 -> 2 -> 3 -> 4   添加valval -> 1 -> 2 -> 3 -> 4  */ListNode *new_node = new ListNode(val); // 定义一个新的节点new_node->next = head;  // val链接头结点head = new_node;        // 更新头结点size++;                 }void addAtTail(int val) {/*1 -> 2 -> 3 -> 4   添加val1 -> 2 -> 3 -> 4 -> val*/// 如果刚初始化也可以使用这个接口if (size == 0){addAtHead(val);return;}ListNode *cur = head; // 当前指针位置，从head开始while (cur->next != NULL){ // 这里遍历到最后一个节点cur = cur->next;}ListNode *new_node = new ListNode(val); // 定义指向新的节点的指针cur->next = new_node;                   // 链接起来size++; }void addAtIndex(int index, int val) {if (index < 0 || index > size)return;if (index == 0) {addAtHead(val);return;}ListNode *cur = head;for (int i = 0; i < index - 1; i++){cur = cur->next;}// 现在来到要加的前一个ListNode *new_node = new ListNode(val);new_node->next = cur->next;cur->next = new_node;size++;}void deleteAtIndex(int index) {if (index < 0 || index >= size) return;ListNode *cur = head;if (index == 0) {head = head->next;delete cur;--size;return;}for (int i = 0; i < index - 1; i++){cur = cur->next;}// 现在来到要删除的前一个ListNode *tmp = cur->next;cur->next = cur->next->next;delete tmp;size--;}
};int main() {MyLinkedList *myLinkedList = new MyLinkedList();myLinkedList->addAtHead(1);myLinkedList->addAtTail(3);myLinkedList->addAtIndex(1, 2);std::cout << myLinkedList->get(1) << std::endl;myLinkedList->deleteAtIndex(1);std::cout << myLinkedList->get(1) << std::endl;delete myLinkedList;return 0;
}

4. 反转链表

4.1 双指针法

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *cur = head; // 定义当前位置指针ListNode *prev = NULL; // 定义当前位置指针while (cur != NULL){ListNode *next_node = cur->next;cur->next = prev;     // 这里链接起来           prev = cur;           // prev上一位cur = next_node;      // cur上一位}return prev;}
};

递归的写法，复习一下递归

class Solution {
public:ListNode* reverse(ListNode* prev, ListNode* cur){if (cur == NULL)return prev;ListNode *next_node = cur->next;cur->next = prev;return reverse(cur, next_node);}public:ListNode* reverseList(ListNode* head) {return reverse(NULL, head);}
};

完整的代码

#include <iostream>struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:ListNode* reverse(ListNode* prev, ListNode* cur){if (cur == NULL)return prev;ListNode *next_node = cur->next;cur->next = prev;return reverse(cur, next_node);}public:ListNode* reverseList(ListNode* head) {return reverse(NULL, head);}
};// 辅助函数：打印链表
void printList(ListNode* head) {ListNode* current = head;while (current != nullptr) {std::cout << current->val << " ";current = current->next;}std::cout << std::endl;
}int main() {Solution solution;// 示例ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);std::cout << "Original List: ";printList(head);ListNode* newHead = solution.reverseList(head);std::cout << "Reversed List: ";printList(newHead);return 0;
}
http://www.lryc.cn/news/149555.html

相关文章：

  • Wordpress 安装插件和主题报错
  • Spring Cloud 2022.x版本使用gateway和nacos实现动态路由和负载均衡
  • CSS中如何隐藏元素但保留其占位空间（display:none vs visibility:hidden）？
  • 无涯教程-机器学习 - 数据可视化
  • springboot设置日志输出级别
  • buildAdmin的使用笔记
  • RealVNC配置自定义分辨率（AlmaLinux 8）
  • LA@特征值和特征向量的性质
  • Springboot使用kafka事务-生产者方
  • 您的计算机已被.halo勒索病毒感染？恢复您的数据的方法在这里！
  • 生成式AI颠覆传统数据库的十种方式
  • el-date-picker自定义只能选中当前月份和半年内月份等
  • Pyecharts教程(十一)：使用Pyecharts绘制带有滑动数据缩放功能的K线图
  • 2023年高教社杯数学建模思路 - 案例：ID3-决策树分类算法
  • POJ 3273 Monthly Expense 二分
  • 图论(基础)
  • docker的运行原理
  • vue自定义键盘
  • k8s 安装 kubernetes安装教程 虚拟机安装k8s centos7安装k8s kuberadmin安装k8s k8s工具安装 k8s安装前配置参数
  • 2023年高教社杯数学建模思路 - 案例：感知机原理剖析及实现
  • OTFS-ISAC雷达部分最新进展（含matlab仿真＋USRP验证）
  • Cell | 超深度宏基因组！复原消失的肠道微生物
  • Centos7 设置代理方法
  • Android versions (Android 版本)
  • LNMP 平台搭建（四十）
  • pcie 6.0/7.0相对pcie 5.0的变化有哪些？
  • 百度Apollo：自动驾驶技术的未来应用之路
  • C++之std::distance应用实例(一百八十八)
  • 中国建筑出版传媒许少辉八一新书乡村振兴战略下传统村落文化旅游设计日
  • 基于java Swing 和 mysql实现的购物管理系统（源码+数据库+说明文档+运行指导视频）