算法Day04_203.移除链表元素

本文主要是介绍算法Day04_203.移除链表元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

203.移除链表元素

题目

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

提示：

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

思路

暴力解法
循环判断，与val相等，就移除操作，将节点next指针直接指向下下一个节点。

若删除的为头结点，那就将头结点向后移动一位就可以。

虚拟头结点解法
给链表添加一个虚拟头结点为新的头结点，如果删除的为头结点，就按照移除元素处理就行，无需其他特殊处理。

解法

暴力解法

代码示例：

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}while (head != null && head.val == val) {head = head.next;}ListNode currentNode = head;while (currentNode != null) {while (currentNode.next != null && currentNode.next.val == val) {currentNode.next = currentNode.next.next;}currentNode = currentNode.next;}return head;}
}

时间复杂度: O(n)
空间复杂度: O(1)

虚拟头结点解法

代码示例：

class Solution {public ListNode removeElements(ListNode head, int val) {if (head==null) {return head;}ListNode preHead=new ListNode(-1,head);ListNode preNode=preHead;ListNode nextNode=head;while (nextNode!=null) {if (nextNode.val==val) {preNode.next=nextNode.next;}else{preNode=nextNode;}nextNode=nextNode.next;}return preHead.next;}
}