203. 移除链表元素

203. 移除链表元素

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

示例：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

思路： 搞一个链表，以第一个值不等于传入整数val的结点为头节点，再创建一个尾结点；来串联所有值不等于val的节点；最终返回新链表的头节点

class Solution {

    public ListNode removeElements(ListNode head, int val) {
       
       if(head==null) return head;

       ListNode newHead = null;//新链表的头结点
       ListNode newTail = null;//新链表的尾结点

       while(head != null) {
         if(head.val != val) {
             //等于空说明头尾结点都是空
             if(newTail == null) {
                 newHead = head;
             }else {
                 //将head拼接到newTail的后面
                 newTail.next = head;
             }
            newTail = head;
         }

         //下一个结点
         head = head.next;
       }

       if(newTail!=null) {//尾结点要清空
           newTail.next = null;
       }else {//newTail==null 意味着传入的链表所有结点都是要删的
           return null;
       }

       //返回新的头节点
       return newHead;

    }

}

优化思路：使用虚拟头节点

class Solution {

    public ListNode removeElements(ListNode head, int val) {

       //0.边界处理
       if(head==null) return head;
       
       //1.定义虚拟头结点
       ListNode newHead = new ListNode(0);
       ListNode newTail = newHead;

       //2.遍历传入的链表 给新链表赋值
       while(head != null) {
           if(head.val != val) {
               newTail.next = head;//将结点拼接到尾结点后面
               newTail = head;//更新尾结点
           }
           head = head.next;
       }

       //3.清空尾结点
       newTail.next = null;
       //4.返回虚拟头节点的下一个节点
       return newHead.next;

    }

}

虚拟头结点步骤最少解法

class Solution {

    public ListNode removeElements(ListNode head, int val) {
          
          if(head==null) return head;

          //0 <= val <= 50 所以用-1
          ListNode dummyHead = new ListNode(-1);
          dummyHead.next = head;
          ListNode prev = dummyHead;
          
          while(prev.next != null) {
                //相等就删除该结点
                if(prev.next.val==val) {
                   prev.next = prev.next.next;
                }else {//不相等就继续
                   prev = prev.next;
                }
          }

          return dummyHead.next;

    }
    
}