行业知识
day3-链表
今日任务 :链表
-
��表理论基础
() -
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]
普通思路
-
直接使用原有链表进行操作:
-
找到目标节点的上一个节点,然后跳过目标节点,用上一个节点的指针,直接指向下一个节点。
-
但如果是要移除头结点,该怎么做?
-
直接把指向头结点的指针,往后移动一位,指向下一个节点。也就是把下一个节点作为新的头结点。
-
优化思路:虚拟头结点
-
新增一个dummy_head 在链表的最前面
-
这样删除链表的任意元素,都可以用统一的方法来删除
伪代码:不使用虚拟头结点
// 不使用虚拟头结点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:
-
所以你的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--;
-
-
-
-
-
-
-
-
-