Удаление нескольких узлов из связанного списка java

Question

Я пытаюсь удалить многократные узлы, которые соответствуют критериям из связанного списка. Программа немного сложна, поэтому я получу ее суть. Узлы в моем связанном списке имеют следующие характеристики (имя, связанное с номером):

Name Number 
Dog  1 
Cat  1 
Rat  2 
Donkey 3 
Fish 1 

Я хочу, чтобы иметь возможность удалить узлы с номером 1. Моей функции удаления:

public void Delete(Int N) { 

     Node current = Head; 
     Node previous = Head; 


     while (current.getNum() != N) { 

      if (current.getNextNode() == null) { 

       System.out.print("Not found"); 

      } else { 

       previous = current; 

       current = current.getNextNode(); 

      } 

     } 

     if (current == Head) { 

      Head = Head.getNextNode(); 

     } else { 

      Node A = current.getNextNode(); 
      previous.setNextNode(A); 

     } 

    } 

Это работает, но только удаляет первое вхождение. Я знаю, это может быть из-за отсутствия или соответствующей структуры петли, но я работал над этим в течение нескольких часов, и я смущаюсь по пути. Я попытался сделать таблицу трассировки вручную, но это тоже не работает.

Как отредактировать функцию, чтобы она проходила по всем связанным спискам и удаляла узлы, соответствующие критериям?

Answer 1

Ваш цикл while (current.getNum() != N) закончится после первого появления узла, который имеет номер N. Если вы хотите, чтобы пройти через весь список то петля должна выглядеть так:

while (current != null) { 
    //do something with the list 
    current = current.getNextNode(); 
} 

В частности, для этого случая вы хотите удалить узел.

Node prev = null; 
while (current != null) { 
    Node next = current.getNextNode() 
    if(current.getNum() == N){ 
     //condition to remove current node has been found. 
     if(prev == null){ 
      Head = next; 
     } else { 
      prev.setNextNode(next); 
     } 
    } else { 
     //only advance prev if we haven't deleted something 
     prev = current; 
    } 
    current = current.getNextNode(); 
} 

Answer 2

Это должно удалить соответствующие Node экземпляры из связанного списка:

public void delete(int n) { 

    int count = 0; 

    Node prev = null, next; 
    for (Node current = head; current != null; current = next) { 
     next = current.getNextNode(); 
     if (current.getNum() == n) { 
      count++; 
      if (prev != null) { 
       prev.setNextNode(next); 
      } else { 
       head = next; 
      } 
     } else { 
      prev = current; 
     } 
    } 

    System.out.print(count > 0 ? ("Number deleted: " + count) : "Not found"); 
} 

Answer 3

Если вы хотите, чтобы удалить узел в вашем LinkedList, вы можете использовать любой из следующих способов

1. новый связанный список только с узлами, в которых число не равно N
2. или изменить существующий.

Я использовал первый способ, создавая новый связанный список с элементом, в котором число не равно N.

class Node { 

    public String name; 
    public int number; 
    public Node next; 
} 

public class LinkedListTest { 

    public static void main(String[] args) { 

     LinkedListTest obj = new LinkedListTest(); 
     Node head = obj.createLinkList(); 
     Node startPointer = head; 
     while (startPointer != null) { 

      System.out.println(startPointer.name + " " + startPointer.number); 
      startPointer = startPointer.next; 
     } 
     System.out.println("***********"); 
     Node newNodeHead = obj.deleteNode(1, head); 
     startPointer = newNodeHead; 
     while (startPointer != null) { 

      System.out.println(startPointer.name + " " + startPointer.number); 
      startPointer = startPointer.next; 
     } 

    } 

    public Node deleteNode(int n, Node head) { 

     Node current = head; 
     Node newNodestartPointer = null; 
     Node newNodeCurrent = null; 
     while (current != null) { 

      if (!(current.number == n)) { 

       if (newNodestartPointer == null) { 
        newNodestartPointer = new Node(); 
        newNodestartPointer.name = current.name; 
        newNodestartPointer.number = current.number; 
        newNodestartPointer.next = null; 
        newNodeCurrent = newNodestartPointer; 
       } else { 

        Node newNode = new Node(); 
        newNode.name = current.name; 
        newNode.number = current.number; 
        newNodeCurrent.next = newNode; 
        newNodeCurrent = newNode; 
       } 
      } 
      current = current.next; 
     } 

     return newNodestartPointer; 
    } 

    public Node createLinkList() { 

     Node head = null; 

     Node newNode = new Node(); 
     newNode.name = "Dog"; 
     newNode.number = 1; 
     newNode.next = null; 

     head = newNode; 

     newNode = new Node(); 
     newNode.name = "Cat"; 
     newNode.number = 1; 
     newNode.next = null; 
     head.next = newNode; 
     Node prevNode = newNode; 

     newNode = new Node(); 
     newNode.name = "Rat"; 
     newNode.number = 2; 
     newNode.next = null; 
     prevNode.next = newNode; 
     prevNode = newNode; 

     newNode = new Node(); 
     newNode.name = "Donkey"; 
     newNode.number = 3; 
     newNode.next = null; 
     prevNode.next = newNode; 

     return head; 
    } 
}