数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Java程序：删除循环链表中间节点
在这个数据结构与算法(DSA)问题中，我们将学习如何删除循环链表中的中间节点。
删除循环链表中的中间节点与删除普通链表中的中间节点方法类似。我们需要找到中间节点的前一个和后一个节点，并将它们直接连接起来以删除中间节点。
问题陈述
我们有一个循环链表，需要删除链表中的中间节点。如果链表包含偶数个节点，则第(N/2)个节点是中间节点。
示例
输入
90 32 67 84 23 78
输出
90 32 84 23 78
解释
67被删除，因为它是一个中间节点。
输入
90 32 84 23 78
输出
90 32 23 78
解释
84被删除，因为它是一个中间节点。
方法一
首先需要计算链表中节点的总数。如果节点总数为偶数，则删除第(N/2)个节点。否则，如果节点总数为奇数，则中间节点为(N/2)+1个节点。
我们需要找到中间节点的前一个节点，并将其下一个指针的值更新为中间节点的下一个指针的值，从而删除中间节点。
算法
步骤1 - 定义名为'dataNode'的类，其中包含整数类型的'val'变量和'dataNode'类型的next指针。
步骤2 - 定义名为'listSize'的静态变量来存储链表的大小。同时，定义'root'和'end'指针来存储第一个和最后一个节点。
步骤3 - 接下来，定义该类的构造函数来初始化'root'和'end'节点，并将列表的大小初始化为0。
步骤4 - 定义addToList()函数向循环链表添加节点。
步骤4.1 - 在addToList()函数中，使用给定值定义'newNode'类型的dataNode。
步骤4.2 - 如果root节点为空，则使用newNode更新root和end节点。同时，将newNode的next指针指向root节点。
步骤4.3 - 否则，将最后一个节点的next指针指向newNode。同时，更新'end'指针的值，并将最后一个节点的next指针指向'root'节点。
步骤4.4 - 添加节点后，将'listSize'加1。
步骤5 - 定义middleDeletion()函数来删除中间节点。
步骤5.1 - 如果'listSize'是偶数，则将mid初始化为'listSize/2'。否则，将mid初始化为(listSize/2) + 1。
步骤5.2 - 如果root为空，则执行返回。
步骤5.3 - 如果root和end相等，则将root和end指针更新为空。
步骤5.4 - 如果mid等于1，则将root节点更新为end节点，并将end节点的next指针更新为end。
步骤5.5 - 在其他情况下，将'curr'初始化为root节点，'previous'初始化为空，p初始化为1。
步骤5.6 - 使用循环进行迭代，直到p小于mid。在循环中，将previous更新为'curr'，'curr'更新为其下一个节点，并将p的值加1。
步骤5.7 - 之后，将'previous'节点的next指针更新为'curr'节点的next指针。同时，将'curr'设置为null，并将listSize减1。
步骤6 - 定义showList()函数来打印列表。
步骤6.1 - 在函数中，使用do-while循环遍历列表，并打印每个节点的值。
步骤7 - 现在，使用addToList()方法向链表添加节点。
步骤8 - 使用middleDeletion()函数删除中间元素，并使用showList()函数打印更新后的列表的元素。
示例
public class Main {
class dataNode {
int val;
dataNode next;
}
private static int listSize;
private dataNode root, end;
// Class constructor
Main() {
this.root = null;
this.end = null;
listSize = 0;
}
public void addToList(int val) {
// New node creation
dataNode newNode = new dataNode();
// For empty list
if (this.root == null) {
newNode.val = val;
this.root = newNode;
this.end = newNode;
newNode.next = this.root;
}
// Append new node at last of the list. connect end node with the root node
else {
newNode.val = val;
end.next = newNode;
end = newNode;
end.next = root;
}
listSize++;
}
public void middleDeletion() {
int mid;
dataNode curr, previous;
// Middle position calculation
if (listSize % 2 == 0) {
mid = listSize / 2;
} else {
mid = (listSize / 2) + 1;
}
// For an empty list
if (root == null) {
return;
}
// For a list having a single node
else if (root == end) {
root = null;
end = null;
}
// For list having two nodes
else if (mid == 1) {
root = end;
end.next = end;
}
// For a list having three or more nodes
else {
curr = root;
previous = null;
int p = 1;
// Reach to the middle node
while (p < mid) {
previous = curr;
curr = curr.next;
p++;
}
// Join the previous node with next node of middle
previous.next = curr.next;
curr = null;
}
listSize--;
if (listSize < 0) {
listSize = 0;
}
}
public void showList() {
// For an empty list
if (root == null) {
System.out.println("The list is empty");
} else {
dataNode curr = root;
// Traverse the linked list
do {
System.out.print(curr.val + " ");
curr = curr.next;
} while (curr != root);
System.out.println();
}
}
public static void main(String args[]) {
Main obj = new Main();
// Add nodes
obj.addToList(90);
obj.addToList(32);
obj.addToList(67);
obj.addToList(84);
obj.addToList(23);
obj.addToList(78);
System.out.print("Initial list is: ");
obj.showList();
// Middle node deletion
obj.middleDeletion();
System.out.print("The updated list after deleting the middle node is: ");
obj.showList();
// Middle node deletion
obj.middleDeletion();
System.out.print("The updated list after deleting the middle node is: ");
obj.showList();
}
}
输出
Initial list is: 90 32 67 84 23 78 The updated list after deleting the middle node is: 90 32 84 23 78 The updated list after deleting the middle node is: 90 32 23 78
时间复杂度 - O(N) 用于查找中间元素。
空间复杂度 - O(1)，因为我们使用了常量空间。
逻辑部分是找到中间节点的前一个和后一个节点，并将它们连接起来以删除中间节点。程序员也可以练习从循环链表中删除起始或结束节点。
浏览量：134
