java 链表 删除第一个节点失败

Question

1 问题

尝试实现链表的删除，删除找到的第一个节点，但是如果要删除的节点是第一个节点就没有结果，删除其它位置的节点就可以。在方法内部可以看到已经修改了指向，但返回以后没有修改。

下图是在findAndDeleteFirst准备返回时listNode的值

下图是findAndDeleteFirst返回后listNode的值

# 2 运行结果

# 3 用到的代码

3.1 ListNode.java

public class ListNode {
    int val;
    ListNode next;
    public ListNode(int value) {
        val=value;
    }
}

3.2 ListNodeUtil.java

public class ListNodeUtil {
    // 向链表的末尾添加节点
    public static void addListNode(ListNode listNode, int x) {
        // 是否为空链表
        if (listNode == null) {
            // 空链表
            listNode = new ListNode(x);
            return;
        }
        // 非空 遍历到链表的末尾
        while (listNode.next != null) {
            listNode = listNode.next;
        }
        // 新建节点并插入
        ListNode newNode = new ListNode(x);
        listNode.next = newNode;
        return;
    }

    // 找到第一个含有某值并删除该节点
    public static boolean findAndDeleteFirst(ListNode listNode, int x) {
        // 链表是否为空
        if (listNode == null)
            return false;
        // 删除的节点在第一个
        if (listNode.val == x) {
            // 将链表头指向下一个节点
            listNode = listNode.next;
            return true;
        }
        // 删除需要有一个指针指向前一个节点，一个指针指向当前节点
        ListNode curNode = listNode;
        ListNode preNode = null;
        while (curNode.next != null) {
            //移动指针
            preNode=curNode;
            curNode=curNode.next;
            //判断是否是当前指针
            if(curNode.val==x) {
                //将前节点的next直接指向下一个节点
                preNode.next=curNode.next;
                return true;
            }
        }
        return false;
    }

    public static void showListNode(ListNode listNode) {
        if(listNode==null) {
            System.out.println("链表为空");
        }else {
            System.out.print(listNode.val+"--->");
            while(listNode.next!=null) {
                listNode=listNode.next;
                System.out.print(listNode.val+"--->");
            }
            System.out.println(" ");
        }

    }
}

3.3 ListNodeMain.java

public class ListNodeMain {
    public static void main(String[] args) {
        //新建、显示
        ListNode listNode=new ListNode(1);
        ListNodeUtil.showListNode(listNode);
        //删除、显示
        ListNodeUtil.findAndDeleteFirst(listNode, 1);
        ListNodeUtil.showListNode(listNode);
        //插入、显示
        ListNodeUtil.addListNode(listNode, 2);
        ListNodeUtil.showListNode(listNode);
        ListNodeUtil.addListNode(listNode, 3);
        ListNodeUtil.addListNode(listNode, 4);
        ListNodeUtil.addListNode(listNode, 5);
        ListNodeUtil.showListNode(listNode);
        System.out.println("删除第一个");
        ListNodeUtil.findAndDeleteFirst(listNode, 1);
        ListNodeUtil.showListNode(listNode);
        System.out.println("删除第二个");
        ListNodeUtil.findAndDeleteFirst(listNode, 2);
        ListNodeUtil.showListNode(listNode);
    }

}

Answer 1

看来你对引用的理解不够深刻啊。
// 删除的节点在第一个
if (listNode.val == x) {
// 将链表头指向下一个节点
listNode = listNode.next;
return true;
}
你是意思是将listNode引用 指向下一个。可是你要知道进入方法之后 listNode只是一个引用副本，你改变这个引用副本对调用方法处的
ListNodeUtil.findAndDeleteFirst(listNode, 1);
也就是方法外部的listNode是没有任何影响的。换句话说，你只是改变了一个临时参数的值而已。
所以除非你把代码粘贴到main里，不然不可能改变listNode(main里的)指向的节点。

所以真要实现删除第一个节点，得在main里新增一个头结点。而showListNode的时候不展示这个头结点。

public class ListNodeMain {
    public static void main(String[] args) {
        //新建、显示
        ListNode listNode = new ListNode(-1); // 头结点
        ListNodeUtil.addListNode(listNode, 1);
        ListNodeUtil.showListNode(listNode);
        //删除、显示
        ListNodeUtil.findAndDeleteFirst(listNode, 1);
        ListNodeUtil.showListNode(listNode);
        //插入、显示
        ListNodeUtil.addListNode(listNode, 2);
        ListNodeUtil.showListNode(listNode);
        ListNodeUtil.addListNode(listNode, 3);
        ListNodeUtil.addListNode(listNode, 4);
        ListNodeUtil.addListNode(listNode, 5);
        ListNodeUtil.showListNode(listNode);
        System.out.println("删除值为1的节点");
        ListNodeUtil.findAndDeleteFirst(listNode, 1);
        ListNodeUtil.showListNode(listNode);
        System.out.println("删除值为2的节点");
        ListNodeUtil.findAndDeleteFirst(listNode, 2);
        ListNodeUtil.showListNode(listNode);
    }

}

class ListNodeUtil {
    // 向链表的末尾添加节点
    public static void addListNode(ListNode listNode, int x) {
        // 非空 遍历到链表的末尾
        while (listNode.next != null) {
            listNode = listNode.next;
        }
        // 新建节点并插入
        listNode.next = new ListNode(x);
    }

    // 找到第一个含有某值并删除该节点
    public static boolean findAndDeleteFirst(ListNode listNode, int x) {
        // 删除需要有一个指针指向前一个节点，一个指针指向当前节点
        ListNode curNode = listNode;
        ListNode preNode;
        while (curNode.next != null) {
            //移动指针
            preNode = curNode;
            curNode = curNode.next;
            //判断是否是当前指针
            if (curNode.val == x) {
                //将前节点的next直接指向下一个节点
                preNode.next = curNode.next;
                return true;
            }
        }
        return false;
    }

    public static void showListNode(ListNode listNode) {
        if (listNode.next == null) {
            System.out.println("空列表！");
            return;
        }
        while (listNode.next != null) {
            listNode = listNode.next;
            System.out.print(listNode.val + "--->");
        }
        System.out.println();
    }
}

class ListNode {
    int val;
    ListNode next;
    public ListNode(int value) {
        val = value;
    }
}