java - 什么是 Java 中的 LinkedListNode

Question

请原谅我的无知，但我开始准备我的第一次技术面试，并在主题链表上遇到了这个问题和答案

问题:实现一个算法来删除单链表中间的节点，只允许访问该节点

public static boolean deleteNode(LinkedListNode n) {if (n == null || n.next == null) {   return false; // Failure}LinkedListNode next = n.next;n.data = next.data;n.next = next.next;return true;}

我想开始使用这段代码(进行更改编译测试)，但我不确定如何在 Java 中开始这样做。我在 Java 文档中找不到 LinkedListNode 类。

这可能是一个非常愚蠢的问题，但如果有人能指出我正确的方向 - 将不胜感激。

编辑

感谢您快速而有用的回复。我想我的问题不是很清楚。上面的算法是作为该问题的解决方案提供的。我想知道如何在 Java 中实现它，以便我可以使用代码。

谢谢

Answer 1

只有当列表中有尾节点时，代码才能正常工作。

算法按照以下逻辑运作

When referring to the node to be deleted, call it "curr"
When referring to the node before "curr", call it "prev"
When referring to the node after "curr", call it "next"

To effectively delete our node, "prev".next should point to "next"
It currently points to "curr"

Our problem is that we have no reference to "prev"

We know "prev".next points to "curr"

Since we cannot change the fact that "prev".next points to "curr",
we must have "curr" gobble up "next"

We make "curr"s data be "next"s data
We make "curr"s next be "next"s next

The reason this only works if there's a tail guard 
is so we can make "next" be the "tail" node of the 
list. (Its data is null and it's next is null.) Otherwise, 
"prev".next would still be pointing to something.

这是一个使用 LinkedListNode 的类。我应该指出，如果你申请的是程序员的职位，你应该基本上可以凭内存来完成。 :-)

class LinkedList<E> {

    static class LinkedListNode<E> {
        E data;
        LinkedListNode<E> next;
    }

    /**
     * Not exactly the best object orientation, but we'll manage
     */
    static <E> E deleteNode(LinkedListNode<E> node) {
        if(node == null || node.next == null) return null;

        E retval = node.data;
        LinkedListNode<E> next = node.next;
        node.data = next.data;
        node.next = next.next;
        return retval;
    }

    private LinkedListNode<E> head;
    private LinkedListNode<E> tail;

    public LinkedList() {
        this.head = new LinkedListNode<E>();
        this.tail = new LinkedListNode<E>();
        head.next = tail;
    }

    public void addLast(E e) {
        LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null
        tail.data = e;
        tail.next = node;
        tail = node;
    }

    public void addFirst(E e) {
        LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null;
        node.next = head.next;
        node.data = e;
        head.next = node;
    }

    public E deleteFirst() {
        LinkedListNode<E> first = head.next;
        head.next = first.next;
        return first.data;
    }

    public E deleteLast() {
        // cannot do without iteration of the list! :-(
        throw new UnsupportedOperationException();
    }

    public LinkedListNode<E> findFirst(E e) {
        LinkedListNode<E> curr = head.next;
        while(curr != null) {
            if(curr.data != null && curr.data.equals(e)) return curr;
            curr = curr.next;
        }
        return null;
    }

    public void print() {
        LinkedListNode<E> curr = head.next;
        while(curr.next != null) {
            System.out.println(curr.data);
            curr = curr.next;
        }
    }


    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.addLast("Apple");
        list.addLast("Bear");
        list.addLast("Chair");
        list.addLast("Dirt");

        //list.print();

        LinkedListNode<String> bear = list.findFirst("Bear");
        deleteNode(bear);

        list.print();
    }

}