Java:从链表中删除节点

Question

我试图在java中删除链表中的一个节点，但在尝试使用deletenode（）方法时，我不断收到NullPointerException

I get the following error trace:
Exception in thread "main" java.lang.NullPointerException
at linkedlist.LinkedList.deletenode(LinkedList.java:44)
at linkedlist.LinkedList.main(LinkedList.java:69)
/Users/carsongedeus/Library/Caches/NetBeans/8.2/executor-snippets/run.xml:53: 
Java returned: 1
BUILD FAILED (total time: 3 seconds)


package linkedlist;

import java.util.Scanner;

/**
 *
 * @author carsongedeus
 */

class Node {

    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

public class LinkedList {

    Node head;
    Node temp;

在列表的最前面插入

    public Node insertnode(int data) {

        if(head == null) {
            head = new Node(data);
        } else {
            temp = new Node(data);
            temp.next = head;
            head = temp;
        }
        return head;
    }

Delete方法在用户在链表的节点内键入指定的整数后给出NULLPointerException

    public void deletenode(int data) {

        Node trace;
        Node del;

        for(trace = head; trace != null; trace = trace.next) {

            if(trace.next.data == data) {
                del = trace.next;
                trace = trace.next.next;
                del.next = null;
            }
        }
    }

打印机

    public void printer() {
        System.out.println(head.data);
    }

    public static void main(String[] args) {

        LinkedList linkedlist = new LinkedList();
        Scanner scan = new Scanner(System.in);
        int n;

        for(int i = 0; i < (n = (int)(Math.random()*100+1)); i++) {
            linkedlist.insertnode((int)(Math.random()*100+1));
            linkedlist.printer();
        }

        System.out.println("Delete something: ");
        int input = scan.nextInt();
        linkedlist.deletenode(input);

        for(int j = 0; j < n; j++) {
            linkedlist.printer();
        }
    }
}

Answer 1

public void deletenode(int data) {
    if (head != null && head.data == data) {
        head = head.next; // delete head
        return;
    }
    Node prev = null;
    Node cur = head;
    while (cur != null && cur.data != data) {
        prev = cur;
        cur = cur.next;
    }
    prev.next = cur.next; // delete cur
}

Answer 2

我认为你处理这个问题的方法是错误的。请找到处理链表问题的适当方法

LinkedListNode类：

class LinkedListNode {
    int data;
    LinkedListNode next;
    LinkedListNode(int data) {
        this.data= data;
        this.next=null;
    }
}

开头插入：

 LinkedListNode insertNodeAtBegining(LinkedListNode head, int val) {
        LinkedListNode temp= head;
        head= new LinkedListNode(val);
        head.next=temp;
        return head;
    }

删除节点：

LinkedListNode deleteNode(LinkedListNode head, LinkedListNode node) {
    if(head==null) {
        return head;
    }
    if(head.data==node.data) {
        return head.next;
    }

    LinkedListNode temp=head;
    while(temp.next!=null) {
        if(temp.next.data==node.data) {
            temp.next=temp.next.next;
        }
        temp=temp.next;
    }
    return head;
}

Answer 3

不要声明临时字段：改用局部变量：

public Node insertnode(int data) {

    if(head == null) {
        head = new Node(data);
    } else {
        Node temp = new Node(data);
        temp.next = head;
        head = temp;
    }
    return head;
}

为了回答您的问题，您需要测试trace是否为null，然后尝试访问trace。下一个没有测试痕迹的数据。下一个

试试这样：

public void deletenode(int data) {

    Node prev = null;

    for(Node trace = head; trace != null; trace = trace.next) {

        if(trace.data == data) {
            if (prev == null) {
                head = trace.next;
            } else {
                prev.next = trace.next;
            }
        } else {
            prev = trace;
        }
    }
}

Answer 4

在您的方法中，要删除的节点是trace.next（您指的是del）。这意味着trace的next指针需要更新到trace.next.next，有效地“跳过”要删除的节点（trace.next）。这看起来像：trace.next = trace.next.next

相反，您要做的是通过将trace设置为trace.next.next来修改它本身。我明白这是为了使迭代正常工作，但会弄乱代码的其余部分，因为您丢失了指向需要更新的节点的指针。如果我们修改trace.next，循环将在结束时运行trace = trace.next时适当地推进指针

在Java中，没有更多指向它的引用的对象将从计算机内存中删除——这个过程称为垃圾收集。由于此时我们已经修改了trace.next，因此除了您所做的del变量之外，没有其他要删除的节点引用。一旦该变量在该函数结束时超出作用域，节点将被垃圾收集，而您无需采取进一步行动。你甚至根本不需要del变量；一旦我们通过更新（跳过）旧的trace.next而丢失了对它的引用，就不存在对该节点的进一步引用，垃圾收集器将剔除它

考虑到所有这些因素，您的代码只会变成：

public void deletenode(int data) {

    Node trace;

    for(trace = head; trace != null; trace = trace.next) {

        if(trace.next.data == data) {
            trace.next = trace.next.next;
        }
    }
}