网络建站,土巴兔网站开发,哪家网站建设专业,传统文化网站建设今日总结#xff1a;虽然之前刷过链表#xff0c;但这次做的是有些费力的#xff0c;也有了更深的理解。整理完今天的 Vue 笔记就睡。。。 DAY 3
01. 移除链表元素#xff08;No. 203#xff09;
题目链接#xff1a;https://leetcode.cn/problems/remove-linked-list-… 今日总结虽然之前刷过链表但这次做的是有些费力的也有了更深的理解。整理完今天的 Vue 笔记就睡。。。 DAY 3
01. 移除链表元素No. 203
题目链接https://leetcode.cn/problems/remove-linked-list-elements/description/
代码随想录题解https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
1.1 题目
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回新的头节点 。
示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例 2 输入head [], val 1 输出[ ] 示例 3 输入head [7,7,7,7], val 7 输出[ ] 1.2 笔记
我们要删除一个节点就是让这个节点的上一个节点指向这个节点的下一个节点如下图所示 但我们的链表是一个单向链表我们无法使得这个节点找到它的上一个节点所以这里我们只能去寻找这个节点的下一个节点是不是要去除的然后将这个节点的的 next 指向它的下下个节点同时我们要保证这个节点绝对不能是要去删除的节点那应该如何保证呢
如果头节点是要删除的节点我们直接让头节点向前移动即可如果是其他节点我们要保证它的下一个节点不能是要删除的节点才进行 p p.next 的操作这是为了避免连续出现删除元素的情况如果我们不判断就会出现漏删的情况 也就是我们节点指向的绝对不能是要删除的节点。
另外要注意的是保证本身和 next 不为空即可next.next 为空是有意义的。
1.3 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {// 先去处理头节点的情况保证 p 一开始指向的不是要删除的元素while (head ! null head.val val ) {head head.next;}if (head null) {return null;}ListNode p head; // 指向头节点的指针while (p.next ! null) { // 隐式的包含了 p ! nullif (p.next.val val) {// 删除节点的逻辑p.next p.next.next;} else {// 保证 p.next 不是要删除的元素才能执行这个操作p p.next;} }return head;}
}1.4 拓展 —— 虚拟头节点
虚拟头节点是思想很简单就是多加一个头节点这样让我们对头节点的处理和对正常节点的处理是相同的唯一需要注意的就是返回值应该是虚拟头节点的 下一个 节点。
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode listNode new ListNode(); // 虚拟头节点listNode.next head;
// while (head ! null head.val val ) {
// head head.next;
// }
// if (head null) {
// return null;
// }ListNode p listNode; //指向头节点的指针while (p.next ! null) {if (p.next.val val) {p.next p.next.next;} else {p p.next;}}return listNode.next;}
}02. 设计链表No. 707
题目链接https://leetcode.cn/problems/design-linked-list/description/
代码随想录题解https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
1.1 题目
你可以选择使用单链表或者双链表设计并实现自己的链表。
单链表中的节点应该具备两个属性val 和 next 。val 是当前节点的值next 是指向下一个节点的指针/引用。
如果是双向链表则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类
MyLinkedList() 初始化 MyLinkedList 对象。int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效则返回 -1 。void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度那么该节点会被追加到链表的末尾。如果 index 比长度更大该节点将 不会插入 到链表中。void deleteAtIndex(int index) 如果下标有效则删除链表中下标为 index 的节点。
1.2 笔记
这里采用上面的虚拟头节点进行设计这样设计对我们修改真正的头节点来说非常便利
先来设计一个节点类
class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.valval;}ListNode(int val,ListNode next) {this.valval;this.next next;}
}这里引进一个 size 变量当指定的 index 值没有意义的时候可以很快的返回先来确定 index 错误的时机index 0 或者 index size 下标从 0 开始每次执行和 index 有关的操作的时候都先判断一次。
这里比较重点的是 get() 方法和 addAtIndex() 方法因为上面 size 的约束不用在考虑越界的问题那思考一下从虚拟头节点到我们需要处理的下标的前一个元素需要走多少个 .next 呢需要 size - 1 步这样就写出了我们的方法
public void addAtIndex(int index, int val) {if (index size || index 0) {return;}size;//找到要插入节点的前驱ListNode pred virtualHeadNode;for (int i 0; i index; i) {pred pred.next;}ListNode toAdd new ListNode(val);toAdd.next pred.next;pred.next toAdd;
}注意这里的边界条件要放宽成 index size 因为题目告诉我们可以设置最后一个元素的后一个元素的值。
接下来是 get() 方法的实现
public int get(int index) {if (index 0 || index size) {return -1;}ListNode currentNode virtualHeadNode;//包含一个虚拟头节点所以查找第 index1 个节点for (int i 0; i index; i) {currentNode currentNode.next;}return currentNode.val;
}这里需要注意的还是需要前进的步数。
1.3 代码
class MyLinkedList {ListNode virtualHeadNode new ListNode(); // 虚拟头节点int size;public MyLinkedList() {}public int get(int index) {if (index 0 || index size) {return -1;}ListNode currentNode virtualHeadNode;//包含一个虚拟头节点所以查找第 index1 个节点for (int i 0; i index; i) {currentNode currentNode.next;}return currentNode.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if (index size || index 0) {return;}size;//找到要插入节点的前驱ListNode pred virtualHeadNode;for (int i 0; i index; i) {pred pred.next;}ListNode toAdd new ListNode(val);toAdd.next pred.next;pred.next toAdd;}public void deleteAtIndex(int index) {if (index 0 || index size) {return;}size--;if (index 0) {virtualHeadNode virtualHeadNode.next;return;}ListNode pred virtualHeadNode;for (int i 0; i index ; i) {pred pred.next;}pred.next pred.next.next;}public ListNode getNodeByIndex(int index) {ListNode p virtualHeadNode.next;while (index-- 0 p ! null) {p p.next;}return p;}
}class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val val; }ListNode(int val, ListNode next) { this.val val; this.next next; }
}03. 反转链表No. 206
题目链接https://leetcode.cn/problems/reverse-linked-list/description/
代码随想录题解https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
3.1 题目
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2 输入head [1,2]
输出[2,1]示例 3
输入head []
输出[]3.2 笔记
第一种是使用双指针来做这个题很容易想到用 cur 指针指向需要改变的节点用 pre 指针指向前一个节点再循环更新 cur 和 pre 指向的节点
这时候遇到一个问题就是 cur 的 next 这时候已经写给了 pre 节点那再怎么找到原本的 next 呢所以这里也需要定义一个 tempNode 来协助更新 cur
下面来考虑初始化pre 初始化为 null cur 初始化为 headtemp 也初始化为 null
最重要的是 while 循环的终点容易犯的错误是在 cur 指向最后一个节点时返回 cur 的值这时候返回的是只有最后一个元素的链表因为最后一个元素还未更新应该再进行一次循环也就是 cur 指向 null 的时候我们返回的是 pre。
3.3 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {// 如果只有一个元素直接返回if (head null || head.next null) {return head;}// 初始化ListNode currentNode head;ListNode preNode null;ListNode tempNode null;while (currentNode ! null) { tempNode currentNode.next; currentNode.next preNode;preNode currentNode;currentNode tempNode; }return preNode;}
}
