在带头节点的单链表中，删除所有值为x的节点（Java实现）

梦里梦外; 2022-06-07 02:29 225阅读 0赞

方法一：

public void deleteAllx1(int x){
            Node p = head.next;
            Node q = head;
            while(p != null){
                while(p != null && p.e != x){
                    q = p;
                    p = p.next;
                }
                if(p != null){
                    q.next = p.next;
                    p.next = null;
                    p = null;
                    p = q.next;
                }else{
                    q.next = null;
                }
            }
        }

方法二：用q从头至尾扫描单链表，p指向q前一节点，若q所指节点值为x，则删除，并让q后移一个节点，否则p,q同步后移一个节点。

public void deleteAllx2(int x){
            Node p = head;
            Node q = head.next;
            while(q != null){
                if(q.e == x){
                    p.next = q.next;
                    q = q.next;
                }else{
                    p = q;
                    q = q.next;
                }
            }
        }

方法三：采用尾插法建立单链表，使用r指向尾节点，初始值为头节点，  
用p从头扫描单链表，若节点值为x，将该节点删除，否则将该节点插入到r之后。

public void deleteAllx3(int x){
            Node r = head, p = head.next, q;
            while(p != null){
                if(p.e != x){
       //将其插入到单链表后面
                    r.next = p;
                    r = p;
                    p = p.next;
                }else{
       //删除节点
                    q = p;
                    p = p.next;
                    q = null;
                }
            }
            r.next = null;
        }