小工具知识网

当前位置: 首页 > 行业知识 > day3-链表

行业知识

day3-链表

2026-11-21 02:36:09 来源:互联网转载

今日任务 :链表

  • ��表理论基础

    ()
  • 203.移除链表元素

  • 707.设计链表

    ()

    链表基础

    什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。

    链表的入口节点称为链表的头结点也就是head。

    链表分类

    • 单链表

    • 双链表:

      • 每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。

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

    • 循环链表:

      • 链表首尾相连

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

      cpp 定义链表

      // 单链表struct ListNode {    int val;  // 节点上存储的元素    ListNode *next;  // 指向下一个节点的指针    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数};

      举例:删除链表一个节点

      删除D节点:

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

        • D节点依然存留在内存里,只不过是没有在这个链表里而已。

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

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

              # python 定义链表class ListNode:    def __init__(self, val, next=None):        self.val = val        self.next = next

              203.移除链表元素 [easy]

              建议: 本题最关键是要理解 虚拟头结点的使用技巧,这个对链表题目很重要。

              题目链接:. - 力扣(LeetCode)

              题目

              给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

              示例 1:

              输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]

              普通思路

              1. 直接使用原有链表进行操作:

              2. 找到目标节点的上一个节点,然后跳过目标节点,用上一个节点的指针,直接指向下一个节点。

              3. 但如果是要移除头结点,该怎么做?

                1. 直接把指向头结点的指针,往后移动一位,指向下一个节点。也就是把下一个节点作为新的头结点。

              优化思路:虚拟头结点

              1. 新增一个dummy_head 在链表的最前面

              2. 这样删除链表的任意元素,都可以用统一的方法来删除

              伪代码:不使用虚拟头结点

              // 不使用虚拟头结点while (head!= null && head->val==target){  // 如果链表为1,1,1, 那就需要持续删除头结点:这里要用while  head = head->next;   // 移除头结点  // cpp 要单独释放内存: delete tmp;}​// 删除非头节点cur = head;  // 定义了一个临时指针,指向head,如果没有移除头元素的话,链表的头结点一直都是headwhile(cur!=null && cur->next != null){  if(cur->next == target)    cur->next = cur->next->next;   // A的next直接指向C  else    cur = cur->nrxt}return head; // head 一直都是链表的头结点​// 补充:1. cur要从head开始,因为单向链表无法往前回溯,所以需要保证target有一个上节点才行​

              伪代码:使用虚拟头结点

              链表操作都推荐使用虚拟头结点,可以统一对链表的操作。

              // 使用虚拟头结点​dummy_head = new();dummy_head->next = head;​cur = dummy_head; // 定义一个临时指针,用来指向dummy_headwhile(cur->next != null){  if(cur->next->val == target)    cur->next = cur->next->next; // 可以用统一的规则,用来删除和增加任何节点    else    cur = cur->next;}return dummy_head->next;   // 注意, 这里dummy_head->next指的是新链表的头结点​​补充:  1. 这里的cur必须指向 dummy_head,而不能指向dummy_head->next  2. 因为:如果要删除一个元素,我们必须知道它的上一个指针是什么  3. 返回时,要返回dummy_head->next,表示新链表的头结点,(head有可能已经被我们删了)​

              707.设计链表

              题目

              . - 力扣(LeetCode)

              在链表类中实现这些功能:

              • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。

              • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。

              • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。

              • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。

              • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

                思路

                这道题目设计链表的五个接口:

                • 获取链表第index个节点的数值 (index是从0开始的)

                • 在链表的最前面插入一个节点

                • 在链表的最后面插入一个节点

                • 在链表第index个节点前面插入一个节点

                • 删除链表的第index个节点

                  可以说这五个接口,已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目

                  链表操作的两种方式:

                  1. 直接使用原来的链表来进行操作。

                  2. 设置一个虚拟头结点在进行操作。

                  下面采用的设置一个虚拟头结点(这样更方便一些,大家看代码就会感受出来)。

                  伪代码

                  重点1:

                  • 所以你的cur一定要指向 n 节点的前一个节点

                  • 一定要保证 第n个节点是 cur->next

                  • 这样我们才能用cur来操作(增加或删除)第n个节点

                    重点2:

                    • 一定要先操作右边,再操作左边指向

                      // 1 获取链表第index个节点的数值 (index是从0开始的)cur = dummy_head->next;  // 让这个cur直接指向头结点​while(n) {  // 带入一下,如果n=0:获取头结点的值,看看有没有报错  cur = cur->next;  n--;}return cur->val;   // 2 在链表的最前面插入一个节点A(dummy)   B  C   D(new_node)  new_node = new node();new_node->next = dummy_head->next;  // D先指向B (因为此时你还能通过dummy获得B点的指针)dummy_head->next = new_node; // 再把A指向D,不能反过来size++;  // 3 在链表的最后面插入一个节点A(dummy)  B  C -> null                  D(new_node)​cur = dummy_head;while(cur->next != null){ // cur->next=null 是指向尾部节点的信号  cur = cur->next;  // while遍历,直到到达尾部}cur->next = new_node;​  // 4 在链表第n个节点前面 插入一个节点 (这里用n代表题目中的index了)  A(dummy)  B     n_node   D  -> null            E(new_node)     ​// 重点:- 所以你的cur一定要指向 n 节点的前一个节点 - 只有保证第n个节点是cur->next, 我们才能用cur来操作,在cur->next(n_node)之前插入一个节点。​cur = dummy_head;while(n){ // 寻找第n个节点  cur = cur->next;  n--;}new_node->next = cur->next; // 一定要先更新右侧的边cur->next = new_onde; // 再更新左侧的边size++; // size表示链表长度,增加一个节点,所以size++    // 5 删除链表的第 n 个节点​// 删除n_nodeA(dummy)  B     n_node   D  -> null            E(new_node)  ​// 重点:一定要保证cur->next是我们要删除的第n个节点!​cur = dummy_head;while(n){  cur = cur->next;  n--; // 遍历去找第n个节点}cur->next = cur->next->next;  size--;​

上一篇:风控助理车贷方面的风控部门审核专员要注意哪些问题,工作中需要学习注意的方面是什么。

下一篇:MiXi下载指南,轻松获取应用,畅享体验之旅