Java 程序从循环链表的开头删除节点
在这个 DSA 问题中,我们将学习创建一个循环链表并从其开头删除节点。
循环链表将最后一个节点与第一个节点连接起来。要从链表中移除第一个节点,我们可以将第二个节点设为根节点,并将最后一个节点与第二个节点连接起来。
问题陈述
我们给出了一个循环链表。我们需要删除链表的起始节点。
示例
输入
1 -> 2 -> 3 -> 4 -> 8 -> 10
输出
2 -> 3 -> 4 -> 8 -> 10
解释
我们从开始就删除了节点。
输入
100 -> 103 -> 200 -> 99 -> 56 -> 78 -> 532
输出
103 -> 200 -> 99 -> 56 -> 78 -> 532
解释
循环链表中的第一个节点已被删除。
方法 1
在此方法中,我们将首先创建循环链表。在将节点添加到链表时,我们将最后一个节点与根节点连接起来。此外,在删除第一个节点时,我们将使根节点的下一个节点成为根节点,并将最后一个节点与更新后的根节点连接起来。
算法
步骤 1 - 创建一个"listNode"类,其中包含整数数据类型的"值"和"下一个"listNode 指针。此外,定义构造函数来初始化"value"变量。
步骤 2 - 接下来,定义"root"和"last"指针来存储链接列表的第一个和最后一个节点。
步骤 3 - 现在,定义 addValue() 函数以将节点添加到链接列表。
步骤 3.1 - 使用我们获得的值作为参数创建一个新的 listNode。
步骤 3.2 - 如果根节点为 NULL,则将新节点分配给"root"和"last"节点。另外,将新节点与根节点连接起来。
步骤 3.3 - 如果根节点不为 NULL,则将新节点与最后一个节点连接起来,更新"last"指针的值,并将最后一个节点与根节点连接起来。
步骤 4 - 定义 deleteFirstNode() 函数以从开头删除节点。
步骤 4.1 - 在 deleteFirstNode() 函数中,如果根为空,则执行 return 语句。
步骤 4.2 - 如果根节点和最后一个节点相同,则将根节点和最后一个节点更新为 NULL。
步骤 4.3 - 如果根节点和最后一个节点不同,则用其下一个节点更新根节点,并将最后一个节点与更新后的根节点连接起来节点。
步骤 5 - 定义 showList() 函数以打印列表值。
步骤 5.1 - 使用根节点初始化"temp"节点。
步骤 5.2 - 如果根为 NULL,则打印"列表为空"的消息。
步骤 5.3 - 否则,遍历列表,并打印"temp"节点的值。此外,使用其下一个节点更新"temp"节点。
步骤 6 - 在 main() 方法中,创建 Main 类的对象。
步骤 7 - 通过将 Main 类的对象作为引用,执行 addValue() 方法将节点添加到链接列表中。之后,调用 showList() 显示原始列表。
步骤 8 − 接下来,执行 deleteFirstNode() 函数删除第一个节点,并调用 showList() 方法显示更新后的链接列表。
示例
public class Main {
// 创建链接列表的节点
public class listNode {
int value;
listNode next;
// 构造函数
public listNode(int val) {
this.value = val;
}
}
// Root and last node initialization
public listNode root = null;
public listNode last = null;
// 添加新节点的方法
public void addValue(int val) {
// 创建新的 listNode
listNode newNode = new listNode(val);
// 对于第一个节点
if (root == null) {
root = newNode;
last = newNode;
newNode.next = root;
}
// 在最后一个节点后添加新节点
// 新节点指向根节点
else {
last.next = newNode;
last = newNode;
last.next = root;
}
}
public void deleteFirstNode() {
// 对于空列表
if (root == null) {
return;
}
// 根节点指向下一个节点。最后一个节点指向更新后的根节点
else {
if (root != last) {
root = root.next;
last.next = root;
}
// 对于具有单个节点的列表
else {
root = last = null;
}
}
}
// 显示节点
public void showList() {
listNode temp = root;
if (root == null) {
System.out.println("The list is empty");
} else {
// 遍历列表以显示每个节点的值
do {
System.out.print(" " + temp.value);
temp = temp.next;
} while (temp != root);
System.out.println();
}
}
public static void main(String[] args) {
Main list = new Main();
// 将数据添加到列表
list.addValue(1);
list.addValue(2);
list.addValue(3);
list.addValue(4);
list.addValue(8);
list.addValue(10);
// 打印原始列表
System.out.println("初始列表为: - ");
list.showList();
// 删除第一个节点
list.deleteFirstNode();
System.out.println("删除第一个节点后,列表为: - ");
list.showList();
// 删除第二个节点
list.deleteFirstNode();
System.out.println("删除第二个节点后,列表为: - ");
list.showList();
}
}
输出
初始列表为: - 1 2 3 4 8 10 删除第一个节点后,列表为: - 2 3 4 8 10 删除第二个节点后,列表为: - 3 4 8 10
时间复杂度 − O(1),因为我们在常数时间内修改指针。
空间复杂度 − O(1),因为我们不使用动态空间。
我们学会了从循环链表中删除第一个节点。程序员可能会学会删除循环链表的最后一个节点。在这种情况下,程序员需要将链表的倒数第二个元素与根节点连接起来。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

