首页 文章

删除位于链接列表中间的节点

提问于
浏览 次
0

我试图删除单链表中两个其他节点中间的节点 .

public void deleteAfter(Node del){
        del.next=del.next.next; 
    }

删除指定节点del之后的节点 .
我得到一个空指针异常 . 我认为问题是删除后与其他节点的链接被破坏 . 我怎么能修补它 . 这是我的完整代码：

public class Node{
    public Object item;
    public Node next;
    public Node(){
        item=null;
        next=null;
    }
    public Node(Object x){
        item=x;     
        next=null;
    }

    public void insertAfter(Node after,Object x){
        Node newNode=new Node(x);
        newNode.next=after.next;
        after.next=newNode;
    }
    public void deleteAfter(Node del){//Deletes the node that is after the specified node
        del.next=del.next.next; 
    }
    public static void main (String args[]){
    Node front=new Node(),p=new Node(),q=new Node();
    p.item="green";
    q.item="red";
    p.next=q;
    front=p;
    front.deleteAfter(p);
    front.insertAfter(p,"black");

    front.insertAfter(q,"blue");
    front.insertAfter(q.next,"orange");
    front.deleteAfter(q);
    System.out.println(front.item);
    System.out.println(front.next.item);
    System.out.println(front.next.next.item);
    System.out.println(front.next.next.next.item);
    }
}
java linked-list nodes

4 回答

  • 1

    首先，您的列表应记住最后一个元素或头部 .

    public class YourList{
   Node heaed;
   public YourList(){
      head = null;
  }
  public void insert(Node node){
     if(last == null){
        head = node;
     } 
  }
  public void deleteAfter(Node del){
        if(del.next == head)){
            head = del;
         }
        if(del.next == null){
           //do nothing because there is nothing to delete
        }
        else{
        del.next=del.next.next; 
        }
   }

 }
    回复于
  • 0

    在：

    p.next=q;
    front=p;
    front.deleteAfter(p);
    front.insertAfter(p,"black");

    您已创建一个从 p 开始的双节点链接列表，并将 front 指向它，然后将其缩小到一个节点链接列表，并将其恢复为两个，包括{"green"，"black"} . q 是您稍后操作的单例列表节点 .

    当您从 front 开始打印时，由于它只有两个节点，因此尝试获取第三个节点的 item （不存在）会导致您的异常 .

    你问的问题始于询问你的 deleteAfter() 是否有问题，而且它会无法正确处理任何正确的节点列表，只有一个实际上有一些东西的列表 . 传入空列表或只包含一个节点的列表将导致异常 .

    回复于
  • 0

    您可以先使用两个指针方法找到中间节点，然后删除该节点 .

    public Node findMiddleNode(Node node){
    Node runner = node;
    while(node!=null){
        node = node.next;
        if(node != null){
            node = node.next;
            runner = runner.next;
        }
    }
    return runner;
}

public static boolean deleteNode(Node node){
    if(node==null || node.next==null) return false;
    Node next = node.next;
    node.data = next.data;
    node.next = next.next;

    return true;
}
    回复于
  • 0

    解决方案，首先计算列表的大小并删除n / 2元素 without using two pointers .

    例如，如果给定的链表是1-> 2-> 3-> 4-> 5，则链表应修改为1-> 2-> 4-> 5 . 如果有偶数节点，那么将有两个中间节点，第二个中间元素被删除 . 例如，如果给定的链表是1-> 2-> 3-> 4-> 5-> 6，则应将其修改为1-> 2-> 3-> 5-> 6 .

    public void deleteMiddle() {

    if (head == null) {
        System.out.println("List is emplty");
        return;
    } else if (head.next == null) {
        head = null;
        return;
    } else {
        int count = 0;
        int nodeDeleteIndex = 0;
        Node node = this.head;
        Node temp = this.head;

        // To calculate the list size
        while (node != null) {
            count++;
            node = node.next;
        }
        // getting the n/2 index of the node which needs to be deleted
        nodeDeleteIndex = (count / 2);
        for (int i = 0; i < nodeDeleteIndex - 1; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
    }
}
    回复于

相关问题