H5W3
当前位置:H5W3 > 其他技术问题 > 正文

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

回答

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


本文地址:H5W3 » java 链表 删除第一个节点失败

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址