链表--移除链表元素--力扣203

目录

题目

思路

代码

细节

题目

给你一个链表的头节点 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.被移除的不是头元素

情况二较为简单，直接遍历找到要删除的元素，使要删除元素的前一个值的下一个元素直接等于要删除的后一个元素。

情况一的处理有两种方法

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

直接让链表中的头指针向后移动一格

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

在原来的头指针前面设置一个虚拟指针

代码

/**
 * 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) {
        while(head!=null&&head.val==val){//头节点的值不能为null，因为题中要取出头节点的值，这个情况就是要删除头节点的逻辑代码
//问题1：为什么这里用while而不是if？
head=head.next;
        }
ListNode curr=head;
while(curr!=null){
while(curr.next!=null&&curr.next.val==val){//这里要删除的节点的值也不能为null
curr.next=curr.next.next;
}
curr=curr.next;
}
return head;
    }
}


/*二
*/
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

class Solution {//添加虚拟头节点的方式
    public ListNode removeElements(ListNode head, int val) {
       if (head == null) {//当头节点的值为null也就是说这个链表就是没有，提前返回
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);//因为原来头节点是0，所以这个是-1，遍历数组的时候从虚拟头节点遍历才能包含要删除的对象是头节点的情况
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {//头节点的值不能为null
        if (cur.val == val) {//这个是删除头节点
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;//返回头节点的值，也就是虚拟节点的后一个
}
}

细节

问题1:

假如这个链表是1 1 1 1 1 1，然后恰好要删除元素的值也为1，如果是if的话就进行一次，而我们需要的是一直删除，所以while更合适