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; } }
- 时间复杂度 O(n)
- 空间复杂度 O(1)
