|
来源：LeetCode第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 输出：[]
提示： 列表中的节点数目在范围 [0, 10^4] 内 1 <= Node.val <= 50 0 <= val <= 50
这题让删除节点值等于val的节点，一种常见的方式就是逐个节点判断。但如果head节点的值等于val的时候，我们可能会把链表搞丢，一种最常见的方式就是创建一个dummy节点，让他指向head节点。原理比较简单，我们来看个动画
最后再来看下代码
public ListNode removeElements(ListNode head, int val) {
//创建一个哑结点
ListNode dummy = new ListNode(0);
dummy.next = head;
//前一个节点pre
ListNode pre = dummy;
while (pre.next != null) {
//如果pre.next节点值等于val，就把pre.next节点给删除
if (pre.next.val == val)
pre.next = pre.next.next;
else
pre = pre.next;
}
return dummy.next;
}
这个可以参考595，删除排序链表中的重复元素，我们可以使用尾递归的方式，当递归往回走的时候在进行判断删除，代码如下 public ListNode removeElements(ListNode head, int val) {
//如果为空，直接返回
if (head == null)
return head;
//先删除当前节点后面需要删除的节点
ListNode next = removeElements(head.next, val);
//如果当前节点的值等于val，我们直接返回next
if (head.val == val)
return next;
//返回head节点，注意原来head的next节点可能改变，
//所以这里要重新赋值
head.next = next;
return head;
}
当然也可以改为首递归的方式，就是先判断删除，然后在递归调用
public ListNode removeElements(ListNode head, int val) {
//如果为空，直接返回
if (head == null)
return head;
//先删除
while (head != null && head.val == val)
head = head.next;
if (head == null)
return null;
//递归
head.next = removeElements(head.next, val);
return head;
}
|
