从单链表中间删除节点的Java程序

1 简介

在此程序中，我们将创建一个单链列表并从列表中间删除一个节点。为了完成此任务，我们将计算列表的大小，然后将其除以2得到列表的中点。temp将指向头节点。我们将遍历列表直到达到中点。现在，temp将指向中间节点，而节点当前将指向temp之前的节点。我们删除中间节点，以便当前的下一个节点将指向temp的下一个节点。

考虑上面的示例，上面列表的中点是2。从头到中点迭代temp。现在，temp指向需要删除的中间节点。在这种情况下，Node是需要删除的中间节点。可以通过使节点2的下一个（当前）指向节点3（临时的下一个节点）来删除该节点。将temp设置为null。

2 算法思路

• 创建一个具有两个属性的类Node：data和next。下一个是指向列表中下一个节点的指针。
• 创建另一个类deleteMid，它具有三个属性：head，tail和size，用于跟踪列表中存在的节点数。
• addNode（）将向列表添加一个新节点：
  • 创建一个新节点。
  • 它首先检查head是否等于null，这意味着列表为空。
  • 如果列表为空，则头和尾都将指向新添加的节点。
  • 如果列表不为空，则新节点将被添加到列表的末尾，使得尾部的下一个将指向新添加的节点。这个新节点将成为列表的新尾部。
• 它首先检查标头是否为空（空列表），然后显示消息“列表为空”并返回。
• 如果列表不为空，它将检查列表是否只有一个节点。
• 如果列表中只有一个节点，则它将head和tail都设置为null。
• 如果列表具有多个节点，则计算列表的大小，然后将其除以2得到列表的中点。
• 声明一个节点temp，该temp将指向head，而当前节点的temp将指向该temp之前的节点。
• 遍历列表，直到temp指向中间节点。如果current不指向null，则通过将current_next指向temp的next来删除中间节点（temp）。否则，头和尾都将指向temp旁边的节点，并通过将temp设置为null来删除中间节点。
• 定义一个节点，该节点将初始指向列表的开头。
• 遍历列表，直到当前指向null。
• 通过在每次迭代中使节点指向其旁边的节点来显示每个节点。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class deleteMid{  
  
//Represent a node of the singly linked list  
class Node{  
int data;  
Node next;  
public Node(int data)  
{  
this.data = data;  
this.next = null;  
}  
}  
  
//Represent the head and tail of the singly linked list  
public Node head = null;  
public Node tail = null;  
  
public int size;  
//addNode() will add a new node to the list  
 public void addNode(int data) {  
//Create a new node  
 Node newNode = new Node(data);  
//Checks if the list is empty  
if(head == null) {  
 //If list is empty, both head and tail will point to new node  
head = newNode;  
tail = newNode;  
}  
else {  
//newNode will be added after tail such that tail's next will point to newNode  
tail.next = newNode;  
//newNode will become new tail of the list  
tail = newNode;  
}  
size++;  
}  
//deleteFromMid() will delete a node from the middle of the list  
void deleteFromMid() {  
Node temp, current;  
//Checks if the list is empty  
if(head == null) {  
System.out.println("List is empty");  
return;  
}  
else {  
//Store the mid position of the list  
 int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);  
//Checks whether the head is equal to the tail or not, if yes then the list has only one node.  
if( head != tail ) {  
 //Initially, temp will point to head  
temp = head;  
current = null;  
//Current will point to node previous to temp  
 //If temp is pointing to node 2 then current will point to node 1.  
for(int i = 0; i < count-1; i++){  
current = temp;  
temp = temp.next;  
}  
if(current != null) {  
 //temp is the middle that needs to be removed.  
 //So, current node will point to node next to temp by skipping temp.  
 current.next = temp.next;  
//Delete temp  
 temp = null;  
 }  
 //If current points to NULL then, head and tail will point to node next to temp.  
 else {  
head = tail = temp.next;  
//Delete temp  
temp = null;  
}  
}  
//If the list contains only one element  
 //then it will remove it and both head and tail will point to NULL  
else {  
head = tail = null;  
}  
}  
size--;  
}  
//display() will display all the nodes present in the list  
public void display() {  
//Node current will point to head  
Node current = head;  
if(head == null) {  
System.out.println("List is empty");  
 return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
public static void main(String[] args) {  
  
        deleteMid sList = new deleteMid();  
  
        //Adds data to the list  
        sList.addNode(1);  
        sList.addNode(2);  
        sList.addNode(3);  
        sList.addNode(4);  
  
        //Printing original list  
        System.out.println("Original List: ");  
        sList.display();  
  
        while(sList.head != null) {  
            sList.deleteFromMid();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            sList.display();  
        }  
    }  
}  

输出结果为：

Original List: 
1 2 3 4 
Updated List: 
1 3 4 
Updated List: 
1 4 
Updated List: 
4 
Updated List: 
List is empty