移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解题思路

  1. 排除null
  2. 针对表首：如果表首的值等于val，删除：
    • 如果元素全部被删除，直接返回null
    • 不是就让head等于下一个节点
  3. 针对表中间部分：
    • 记录最后的last节点(方便善后工作)
    • 如果当前now节点的值不等于val，说明应该收藏该节点，令last.next=now，同时让last变为now
  4. 针对表尾善后工作：如果是手写算法，这个环节容易被忽略，上一个步骤最后并未将表尾的等于val的节点删除掉，由于我们记录了最后不等于val的节点，所以我们只要让last的下一个节点为空即可last.next=null

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode removeElements(ListNode head, int val) {
    if(head==null)return null;
    //首部
    while(head.val==val){
        if(head.next==null)return null;
        head=head.next;
    }
    //之后
    ListNode last=head;
    ListNode now=last.next;
    while(now!=null){
        if(now.val!=val){
            last.next=now;
            last=now;
        }
        now=now.next;
    }
    //善后
    last.next=null;
    return head;
}