LeetCode刷题 203移除链表元素

203. 移除链表元素

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

示例 1：

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

题解（双指针）​​​​​​

• 因为头结点跟别的节点不一样，需要特殊处理

  public ListNode removeElements(ListNode head, int val) {
        ListNode node=head;//定义删除结点
        if(head==null){//如果这个链表为空，就直接返回
            return null;
        }
        while (head!=null&&head.val==val){
            //用来删除那些值为val的头结点，
            //可能删了一个头结点，但是下一个结点还是val
            //然后下一个结点变成了头结点，所以用while处理
            head=head.next;
        }
        if (head==null){
            //可能在删除头结点的时候，就将链表删空了
            return null;
        }
        else {
            ListNode prev=head;//前驱结点的定义
            //因为前面的 *** 作，所以头结点的值不可能为val
            while (prev.next!=null){//因为删除的是前驱结点的下一个结点，所以一定要防止为空
                node=prev.next;
                if (node.val==val){
                    prev.next=node.next;
                }
                else {
                    prev=prev.next;
                }
            }
        }
        return head;
    }

题解（双指针带虚拟头结点） 

• 虚拟头结点的存在，使不存在没有前驱结点的结点，所以所有结点都是一个方法处理 

JAVA代码实现

public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead= new ListNode();//定义虚拟头结点
            dummyHead.next=head;//将虚拟头结点跟头结点链接起来
            ListNode prev=dummyHead;//定义前驱结点
            while (prev.next!=null){//因为删除的是前驱结点后面的结点，所以防止为null
                ListNode node=prev.next;
                if (node.val==val){
                    prev.next=node.next;
                    node.next=null;
                }else {
                    prev=prev.next;
                }
            }
            return dummyHead.next;
    }

题解（递归解法）

 

public ListNode removeElements(ListNode head, int val) {
        //先想终止条件，如果链表为空
        if (head == null) {
            return head;
        }
        //将剩余结点让子方法解决
        ListNode nextHead = removeElements(head.next, val);
        //如果头结点为删除的结点
        if (head.val == val) {
            return nextHead;
        } else {//头结点不是删除的结点，就将头结点跟处理好的链表链接
            head.next = nextHead;
            return head;
        }

    }