3

我正在尝试删除链表的最后一个节点，只给出指向该节点的指针。

我写了下面的实现，但是没有用。

我已经访问了有关此主题的大多数 SO 问题，但没有一个显示如何删除链表的最后一个节点，如果只有一个指向该节点的指针？

我在这里错过了什么吗？

class Node {

        Node next;
        int value;

        Node(int val) {
                this.value = val;
                this.next = null;
        }

        @Override
        public String toString() {
                Node cur = this;
                String str = "";

                while(cur != null) {
                        str += cur.value+"->";
                        cur = cur.next;
                }

                return str;
        }
}

class DeleteNodeLL {

    public static void deleteNode(Node current) {
        Node temp;
        if(current.next == null) {
            current = null;
            return;
        } else {
            current.value = current.next.value;
            temp = current.next;
            temp = null;
            current.next = current.next.next;
        }

    }
    public static void main(String [] args) {

        Node n1 = new Node(25);
        Node n2 = new Node(1);
        Node n3 = new Node(36);
        Node n4 = new Node(9);
        Node n5 = new Node(14);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = null;

        System.out.println("Original linkedlist :");
        System.out.println(n1);

        System.out.println();

        System.out.println("After deleting a node :");
        deleteNode(n5);
        System.out.println(n1);
    }
}

输出 ：-

原始链表：
25->1->36->9->14->

删除节点后：
25->1->36->9->14->

4

5 回答 5

5

使用单链表是不可能的。
这是强调数据结构的大人物公司通常会问的面试问题。
问题被表述为“在给定仅指向该节点的指针的情况下删除单链表中的节点”
预期解决方案： 

public void deleteNode(Node n)
{
    if(n==null || n.next==null)
    {
        System.out.println("Delete not possible");
        return;
    }

    n.data = n.next.data;
    Node tmp = n.next;
    n.next = n.next.next;
    tmp.next = null;

    System.out.println("Node Deleted");
}

想法是将数据从下一个节点复制到当前节点并删除下一个节点。如果节点是最后一个节点，则解决方案不起作用（这是候选人在面试中必须辩论和指出的问题）

希望对你有帮助！（您的问题的解决方案是一个技巧问题，它不存在）

于 2013-07-09T04:27:18.267 回答
3

current = null;不符合您的预期 - 它仅将局部变量（方法参数）设置为null.

对于您当前的课程实现，您想要什么是不可能的Node。您需要对Node类中的前一个节点的引用（即双向链表），或者您必须提供对该deleteNode方法的某个前一个节点的引用。

于 2013-07-09T03:25:42.607 回答
0

I would say

You can delete the last node from the Linked List if reference of it's previous node is given.

However it's based on how you implement the list.

For your implementation, you can't do that

于 2013-07-09T06:24:09.510 回答
0

这个问题的唯一解决方案是迭代完整的列表，每次都保持上一个节点指针，比较当前节点和当前节点。当比较通过时，删除最后一个节点，并将prev节点指向null。类似于下面的代码（注意：我没有编译它）

deleteNode(Node *node){
if(node){
currentNode = Head, prevNode = NULL;
while(currentNode != node){
prevNode = currentNode;
currentNode = currentNode -> next;
}
delete currentNode;
prevNode -> next = NULL;
}
}
于 2013-07-12T14:33:26.917 回答
0

@asifsid88 复制并粘贴了“破解编码”中的解决方案，您应该参考该书以找到更多有趣和具有挑战性的问题。

于 2014-03-26T19:25:26.667 回答