xklx_z
虚空来袭
2020-09-04 13:42
采纳率: 100%
浏览 105
已采纳

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

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);
    }

}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • miaoch
    miaoch 2020-09-04 15:43
    已采纳

    看来你对引用的理解不够深刻啊。
    // 删除的节点在第一个
    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;
        }
    }
    
    
    
    点赞 评论
  • dashicaineng
    点赞 评论

相关推荐