数据结构之删除链表中等于定值val的所有结点（4种方法）

短命女 2021-11-17 02:54 220阅读 0赞

class Node{
        int val;
        Node next=null;
        Node(int val){
            this.val=val;
        }
        public String toString(){
            return String.format("(%d)", val);
        }
        //头插
    public static Node pushFront(Node head,int val){
        //head：原来的第一个结点，val要插入放入值
        Node node=new Node(val); //把val装入一个结点中
        node.next=head;//让原来的 head 成为 node 的下一个结点
        head=node;   //让头成为插入进去的结点
        return head; //返回新的第一个结点
        }
    //删除链表中等于定值val的所有结点
      // 方法1:创建一个新链表，遍历原链表把与指定值不相等的移到新链表然后输出
    public static  Node removeElements1(Node head,int val){
        if (head == null) {
            return null;
        }
        Node result = null;//创建一个新的链表的引用
        Node last = null;   // 记录目前 result 中的最后一个结点
        Node cur = head;
        while (cur != null) {//这里开始遍历原链表
            if (cur.val == val) {
                cur = cur.next; //碰见与指定值相等的直接跳过此次循环
                continue;
            }
            Node next = cur.next; //记录下一次要遍历的元素
            cur.next = null; //因为不知道这是不是最后一个结点，所以把这个结点的.next=null;
            if (result == null) {
                result = cur; //result指向链表的头
            } else {
                last.next = cur;  //这里是让新链表的倒数第二个结点连接最后一个结点
            }
            last = cur;  //记录最后一个结点
            cur = next;  //cur开始遍历下一个结点
        }
        return result;
    }
    //方法2：直接在原链表上进行操作，由于删除一个结点必须要知道它的前驱，但是第一个结点往往是没有前驱的，所以我们在前驱问题上有可以有3种不同的实现方法
      //方法2-1：
    public static Node removeElements2_1(Node head,int val) {
            if (head == null) {
              return null;
            }
           Node prev =null;  //定义一个引用，它指向cur指向的结点的前一个结点
           Node cur=head;
           while(cur!=null){
               if (cur.val == val) {
                   if (cur == head) {  //应对cur是头的情况，直接让head指向下一个结点
                       head = cur.next;
                   }
                   else {
                       prev.next = cur.next; //prev直接绕过要删除的结点，让它成为垃圾被回收
                   }
               } else {
                   prev = cur;//如果不是，把prev指向cur指向的结点
               }
               cur=cur.next;
           }
           return head;
        }
        //方法2-2：从第二个结点开始遍历，最后在应对第一个结点的情况
    public static Node removeElements2_2(Node head,int val) {
        if (head == null) {
            return null;
        }
        Node prve=head;
        Node cur=head.next;
        while (cur!=null){
            if(cur.val==val){
                prve.next=cur.next;
            }
            else{
                prve=cur;
            }
            cur=cur.next;
        }
        if(head.val==val){   //如果第一个结点就是要删除的结点，那么直接让head指向下一个结点
            head=head.next;
        }
        return head;
        }
        //方法2-3：定义一个没用的结点头插到原链表里，然后打印的时候从第二个结点开始打印
    public static Node removeElements2_3(Node head,int val) {
        if (head == null) {
           return null;
        }
        Node tmpHead=new Node(0);
        tmpHead.next=head;//头插到原链表里
        Node prev=tmpHead;
        Node cur=head;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
            }else{
                prev=cur;
            }
            cur=cur.next;
        }
        return head;  //这里的head指向的是第二个结点
    }
    }
    public class MyLinkedList {
        public static void main(String[] args){
            Node head=null;  //创建一个空链表
              
            head=Node.pushBack(head,1);
            head=Node.pushBack(head,2);
            head=Node.pushBack(head,6);
            head=Node.pushBack(head,3);
            head=Node.pushBack(head,4);
            head=Node.pushBack(head,5);
            head=Node.pushBack(head,6);
            print(head);
            System.out.println();
            
            Node.removeElements1(head,6);
             print(head)
        }
        //打印函数
        private static void print(Node head){
            System.out.println("打印链表");
            for(Node cur=head;cur!=null;cur=cur.next)
            {
                System.out.print(cur+"-->");
            }
            System.out.print("null");
        }
    在这里插入代码片

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: /images/20211116/7a6685ec6d4f4ebfabc980c1eca1a9d3.png