java - deleteNode 有问题

Question

我的问题是关于需要删除节点的 lintcode 练习，但由于某种原因我的简单程序无法运行。

例如，输入(1->2->3->4->null, 3)应该输出(1->2->4->null)，我的想法是删除下一个节点并“复制”它输入这个节点的值。

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param node: the node in the list should be deleted
     * @return: nothing
     */
    public void deleteNode(ListNode node) {
        // write your code here
        ListNode pnext;
        if (node != null) {
            if (node.next != null) {
                ListNode tempnode = node.next;
                if (node.next.next != null) {
                    pnext = node.next.next;
                }
                else {
                    pnext = null;
                }

                node.next = null; //delete next node
                node = tempnode; // give next node to THIS node
                node.next = pnext; // link next
            }
        }
        else node = null;
    }
}

我对给节点赋予值(value)感到很困惑，node1 = node2 是否有效？我知道 node.val 可以。任何人都可以简单地指导我吗？

Answer 1

您没有在帖子中包含实际发生的情况，也没有包含创建列表的部分，所以我只能假设发生的情况是您没有删除 3，而是删除了 4？或者它根本不删除任何东西？

所以你有一个方法应该删除一个节点，你想删除的节点作为参数给出。但是由于您的列表仅以一种方式链接，因此您无法确定它之前的节点(它包含对要删除的节点的引用)。实际上删除方法应该像这样简单:

public void deleteNextNode(ListNode node) {
    if(node == null || node.next == null) return; //nothing to delete
    if(node.next.next == null){
        node.next = null;
        return;
    } else{
        node.next = node.next.next;
    }
}

虽然我没有测试过。只要您不存储任何其他对节点的引用就足够了，否则您需要在 else 部分显式调用 next.null。

编辑:我的函数删除您传递的节点之后的节点，但您想要一个删除您传递的节点的函数。这里的问题是前一个节点存储了对要删除的节点的引用，但是您无法仅通过对要删除的节点的引用来确定那个节点。因此，要么使用此函数并始终传递前一个节点，要么制作一个包装函数并遍历列表并始终保护前一个节点并使用该节点调用该函数:

public ListNode deleteNode(ListNode start, ListNode deleteMe)
{
    ListNode prev = start;
    if(start == deleteMe) return start.next;
    while(prev.next != null) {
        if(prev.next == deleteMe)
            deleteNextNode(prev);
        prev = prev.next;
    }
    return start;
}

请注意，我让该函数返回一个 ListNode，这始终是列表的第一个节点(以防您决定删除第一个节点)。希望对您有所帮助