无法删除链表中的最后一个节点

Question

我试图从我的单链表中删除最后一个节点。但是我仍然无法解决代码中的这个错误。我的 deleteFromEnd 方法没有删除最后一个节点。调用 delete 方法后，它仍然显示我要删除的节点。删除列表的其余部分，但不会删除最后一个节点本身。你能告诉我我遗漏了什么，或者错误在哪里吗？

链表：

package lab5;

public class LinkedList {

    public static void main(String argsp[]) {
        List ob = new List();

        ob.addAtStart("y", 6);
        ob.addAtStart("w", 4);
        ob.addAtStart("z", 3);

        ob.addAtEnd("a", 3);
        ob.addAtEnd("b", 4);
        ob.addAtEnd("c", 5);

        /*
         * ob.display(); System.out.println("Deleted first one");
         * ob.deleteFromStart();
         */
        ob.display();
        System.out.println("Deleted End one");
        ob.deleteFromEnd();
        ob.display();
    }
}

列表：

package lab5;

public class List {

    Node head;

    public List() {
        head = null;
    }

    public List(Node e) {
        head = e;
    }

    Node oldfirst = null;
    Node lasthead = null;

    public void addAtStart(String name, int age) {
        Node newObject = new Node(name, age);
        newObject.next = head;

        if (oldfirst == null) {
            oldfirst = newObject;
        }
        head = newObject;
        lasthead = head;

    }

    public void display() {
        Node store = head;
        while (store != null) {
            store.display();
            store = store.next;
            System.out.println();
        }
    }

    public void addAtEnd(String name, int age) {
        Node atEndValue = new Node(name, age);
        oldfirst.next = atEndValue;
        oldfirst = atEndValue;
    }

    public void deleteFromStart() {
        if (head.next != null) {
            head = head.next;
        }
    }

    public void deleteFromEnd() {
        Node start = head;
        Node prev = null;
        while (head != null) {
            prev = head;
            head = head.next;
        }
        prev.next = null;
        head = prev;
    }

    public Node search(String name) {
        return head;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        return (head.toString()).length();
    }
}

节点：

package lab5;

public class Node {

    String name;
    int age;
    Node next;

    public Node() {
        name = "Abc";
        age = 10;
        next = null;
    }

    public Node(String name, int age) {
        this.name = name;
        this.age = age;
        next = null;
    }

    public void display() {
        System.out.println("Name: " + name + " Age: " + age);
    }
}

Answer 1

不要改变Linked List的头部，否则你会松散链表。尝试对您的函数进行以下修改：

public void deleteFromEnd() {
        Node start = head;
        Node prev = null;
        if(start == null){
           return;
        }
        if (start.next == null){
           head = null;
           return;
        }
        while (start.next != null) {
            prev = start;
            start = start.next;
        }
        prev.next = null;
    }

Answer 2

你正在修改错误的列表头指针。以下方法对我有用。

   public void deleteFromEnd() {
        Node start = head;
        Node prev = null;

        if(start == null || start.next == null)
        {
            head = null;
            return;
        }
        while (start.next != null) {
            prev = start;
            start = start.next;
        }
        prev.next = null;
    }

在进一步分析您的代码后，我发现了一些其他问题。您需要更新 addAtStart 和 addAtEnd 方法。

Node lasthead = null;

public void addAtStart(String name, int age) {
    Node newObject = new Node(name, age);
    newObject.next = head;
    if(head == null)
        lasthead = newObject;
    else if(head.next == null)
        lasthead = head;

    head = newObject;

}


public void addAtEnd(String name, int age) {
    Node atEndValue = new Node(name, age);
    lasthead.next = atEndValue;
    lasthead = atEndValue;
}

原因是，假设我从列表末尾删除一个节点。我将无法将元素添加到列表的末尾。

Answer 3

当您从单向链表的末尾删除时，您必须执行以下操作：

遍历列表，并创建一个变量来引用列表的倒数第二个元素。
设置倒数第二个节点之后的节点为null

在遍历链表时永远不要更改 head 的值，因为这实际上会删除整个链表。由于您已经覆盖了 head 变量，因此您无法找到返回起点的方法。相反，使用初始化为 head.

的临时变量进行迭代

最后，请记住考虑列表只有 1 个元素或已经为空的边缘情况：

public void deleteFromEnd() {
    Node current = head;
    Node previous = null;

    while (current != null && current.next != null) {
        previous = current;
        current = current.next;
    }

    if (current == head) {
        head = null;
    }

    if (previous != null) {
        previous.next = null;
    }
}

无法删除链表中的最后一个节点

Unable to delete last node in linked list

java

linked-list

singly-linked-list