代码随想录刷题day09|（链表篇）203.移除链表元素
目录
一、链表理论基础
1.链表的定义
不同语言代码不同；以java为例，定义链表结点：
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}2.链表的类型
单链表（只有指向后一结点指针域）、双链表（有指向后一结点指针域、指向前一结点指针域）、循环链表（单链表+首尾相连）、循环双链表（双链表+循环链表）
3. 链表的操作
增删 只需改变该结点的前一结点的指针域值，所以增删中必须知道上一结点；查询操作，需要遍历整个链表；
4.链表的存储方式
和数组连续地址不同，链表在内存中地址的存放不是连续的，而是分散的；
5.链表特点
增删快，查询慢；
二、移除链表元素
删除（添加）链表结点时，一般两种方法：1.在原有链表上直接移除 2.虚拟头结点
法1：在原有链表上直接移除
定义一个临时指针cur，指向头结点，移动cur，遍历整个链表，判断cur指向结点的数值是否为目标值，若是，则改变链表指针域的值，移除该结点，否则，cur继续指向下一结点。
这种方法下，需要判断移除的结点是否为头结点，如果为头结点，那么移除操作为：头结点直接往后移动一个，将下一个结点作为当前的头结点；如果非头结点，移除操作为：将该结点的前一个结点指向该结点的后一个结点。
注意点：
- 首先判断移除的结点是否为头结点，进而要分开讨论两种情况下的操作逻辑；
- 判断要删除的结点是否为头结点 的过程要注意是while还是if，本题是while；
- 无需定义太多指针（front、index等），可以使用 .next.next进行指代；
- 注意判断结点是否为空的情况；
- 最后返回的头结点是原链表头结点；
- 定义临时结点必要性：不可用头结点遍历，否则头结点指向的值始终在变化，无法返回；
法2：虚拟头结点
自定义一个头结点dummy，并使其指向实际头结点head，定义一个临时指针cur进行遍历，寻找和目标值一致的结点，并进行移除操作。
虚拟一个头结点，能够用统一的规则去处理（删除、添加）所有结点（包括头结点），无需再判断被处理结点是否为头结点。
注意点：
- 定义结点的代码书写规范要熟悉；
- 最后返回的头结点，不是原本的头结点head，而是虚拟头结点的下一个结点（这才是经过处理以后的链表的头结点），因为head可能在操作过程中已被移除；
- 易错：注意⚠️2中如果返回dummy，则返回的链表第一个结点值是dummy结点的值（为0）；
- head和head.next不同，前者是head指针指向的（头）结点，后者是head指向的结点的指针域的值，也就是 head指向的结点的下一个结点；
- 定义一个临时指针cur，指向dummy，也即被操作结点的上一个结点；
三、相关算法题目
203.移除链表元素
法1：原有链表直接移除
class Solution {
public ListNode removeElements(ListNode head, int val) {
//原链表上直接删除
ListNode cur;
while(head != null && head.val == val){
//删除结点为头结点
head = head.next;
}
cur = head;//此时head.val != val
//要知道被删除结点的上一个结点
while(cur != null && cur.next != null){
//删除结点为非头结点
if(cur.next.val == val){
cur.next = cur.next.next;
}
else{
cur = cur.next;//只有不等 cur才能移动到下一个结点
}
}
return head;
}
}法2：虚拟头结点
class Solution {
public ListNode removeElements(ListNode head, int val) {
//虚拟头结点
ListNode dummy = new ListNode(); //定义虚拟头结点
dummy.next = head; //指向原本头结点
ListNode cur = dummy;
while(cur.next != null){
//当指向最后一个结点时，上一轮循环会判断该结点的值，所以本轮不会进入while循环
//不管最后一个结点是否为目标结点 最终返回的链表 尾结点均指向null
if(cur.next.val == val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
//return dummy; //报错 链表首个元素值为0
return dummy.next; //返回实际头结点
}
}四、总结
1.注意两种方法对头结点的不同处理；
2.定义临时指针时，指向的结点要想清楚；
3.最后返回的结点要明白；
4.链表的定义要会写；
原文地址：https://blog.csdn.net/m0_64265848/article/details/145193101
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！