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 被删除,因为它是中间节点。
方法 1
第一个任务是计算链接列表中的节点总数。如果总节点数为偶数,则删除第 (N/2) 个节点。否则,如果奇数总数为偶数,我们可以得到中间节点。
我们需要找到中间节点的前一个节点,并用中间节点的下一个指针值更新它的下一个指针值,以删除中间节点。
算法
步骤 1 - 定义包含整数类型的"val"变量和"dataNode"类型的下一个指针的"dataNode"类。
步骤 2 - 定义名为"listSize"的静态变量来存储链接列表的大小。此外,定义"root"和"end"指针来存储第一个和最后一个节点。
步骤 3 - 接下来,定义类的构造函数,用 0 初始化"root"和"end"节点以及列表的大小。
步骤 4 - 定义 addToList() 函数以将节点添加到循环链接列表。
步骤 4.1 - 在 addToList() 函数中,使用给定值定义 dataNode 类型的"newNode"。
步骤 4.2 - 如果根节点为空,则使用 newNode 更新根节点和结束节点。另外,用根节点更新 newNode 的下一个指针。
步骤 4.3 - 否则,将最后一个节点的下一个指针指向 newNode。另外,更新"end"指针值,并用"root"节点更新最后一个节点的下一个指针。
步骤 4.4 - 添加节点后,将"listSize"加 1。
步骤 5 - 定义 middleDeletion() 函数以删除中间节点。
步骤 5.1 - 如果"listSize"为偶数,则用"listSize/2"初始化中间节点。否则,用 (listSize/2) + 1 初始化 mid。
步骤 5.2 - 如果 root 为 null,则执行 return。
步骤 5.3 - 如果 root 和 end 相等,则用 null 更新 root 和 end 指针。
步骤 5.4 - 如果 mid 等于 1,则用 end 节点更新 root 节点,用 end 更新 end 节点的 next 指针。
步骤 5.5 - 在其他情况下,用 root 节点初始化 'curr',用 null 初始化 'previous',用 1 初始化 p。
步骤 5.6 - 使用循环进行迭代,直到 p 小于 mid。在循环中,用"curr"更新前一个节点,用其下一个节点更新"curr",并将 p 的值加 1。
步骤 5.7 − 之后,用"curr"节点的下一个指针更新"previous"节点的下一个指针。此外,将"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;
// 类构造函数
Main() {
this.root = null;
this.end = null;
listSize = 0;
}
public void addToList(int val) {
// 创建新节点
dataNode newNode = new dataNode();
// 对于空列表
if (this.root == null) {
newNode.val = val;
this.root = newNode;
this.end = newNode;
newNode.next = this.root;
}
// 在列表的最后附加新节点。将结束节点与根节点连接起来
else {
newNode.val = val;
end.next = newNode;
end = newNode;
end.next = root;
}
listSize++;
}
public void middleDeletion() {
int mid;
dataNode curr, previous;
// 中间位置计算
if (listSize % 2 == 0) {
mid = listSize / 2;
} else {
mid = (listSize / 2) + 1;
}
// 对于空列表
if (root == null) {
return;
}
// 对于具有单个节点的列表
else if (root == end) {
root = null;
end = null;
}
// 对于具有两个节点的列表
else if (mid == 1) {
root = end;
end.next = end;
}
// 对于具有三个或更多节点的列表
else {
curr = root;
previous = null;
int p = 1;
// 到达中间节点
while (p < mid) {
previous = curr;
curr = curr.next;
p++;
}
// 将前一个节点与中间的下一个节点连接起来
previous.next = curr.next;
curr = null;
}
listSize--;
if (listSize < 0) {
listSize = 0;
}
}
public void showList() {
// 对于空列表
if (root == null) {
System.out.println("列表为空");
} else {
dataNode curr = root;
// 遍历链接列表
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();
// 添加节点
obj.addToList(90);
obj.addToList(32);
obj.addToList(67);
obj.addToList(84);
obj.addToList(23);
obj.addToList(78);
System.out.print("初始列表为: ");
obj.showList();
// 删除中间节点
obj.middleDeletion();
System.out.print("删除中间节点后更新后的列表为: ");
obj.showList();
// 删除中间节点
obj.middleDeletion();
System.out.print("删除中间节点后更新后的列表为: ");
obj.showList();
}
}
输出
初始列表为:90 32 67 84 23 78 删除中间节点后更新的列表为:90 32 84 23 78 删除中间节点后更新的列表为:90 32 23 78
时间复杂度 - O(N) 查找中间元素。
空间复杂度 - O(1),因为我们使用常数空间。
逻辑部分是找到中间节点的前一个和下一个节点,将它们连接起来以删除中间节点。此外,程序员可以练习从循环链表中删除起始或结束节点。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

