数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究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'类，包含整数数据类型的'value'和'next' listNode指针。另外，定义构造函数来初始化'value'变量。
步骤2 − 接下来，定义'root'和'last'指针来存储链表的第一个和最后一个节点。
步骤3 − 现在，定义addValue()函数将节点添加到链表中。
步骤3.1 − 使用我们作为参数获得的值创建一个新的listNode。
步骤3.2 − 如果根节点为NULL，则将新节点分配给'root'和'last'节点。另外，将新节点连接到根节点。
步骤3.3 − 如果根节点不为NULL，则将新节点连接到最后一个节点，更新'last'指针的值，并将最后一个节点连接到根节点。
步骤4 − 定义deleteFirstNode()函数以从开头删除节点。
步骤4.1 − 在deleteFirstNode()函数中，如果root为空，则执行return语句。
步骤4.2 − 如果root和last节点相同，则将root和last更新为NULL。
步骤4.3 − 如果root和last节点不同，则将root节点更新为其下一个节点，并将last节点连接到更新后的root节点。
步骤5 − 定义showList()函数来打印列表值。
步骤5.1 − 使用root节点初始化'temp'节点。
步骤5.2 − 如果root为NULL，则打印消息“列表为空”。
步骤5.3 − 否则，遍历列表并打印'temp'节点的值。另外，使用其下一个节点更新'temp'节点。
步骤6 − 在main()方法中，创建Main类的对象。
步骤7 − 通过将Main类的对象作为引用，执行addValue()方法将节点添加到链表中。之后，调用showList()显示原始列表。
步骤8 − 接下来，执行deleteFirstNode()函数删除第一个节点，并调用showList()方法显示更新后的链表。
示例
public class Main {
// Node for creating the linked list
public class listNode {
int value;
listNode next;
// Constructor
public listNode(int val) {
this.value = val;
}
}
// Root and last node initialization
public listNode root = null;
public listNode last = null;
// Method to add new Node
public void addValue(int val) {
// Cerate new listNode
listNode newNode = new listNode(val);
// For the first node
if (root == null) {
root = newNode;
last = newNode;
newNode.next = root;
}
// Add new node after the last node
// New node points to the root node
else {
last.next = newNode;
last = newNode;
last.next = root;
}
}
public void deleteFirstNode() {
// For an empty list
if (root == null) {
return;
}
// Root node points to the next node. The last node points to the updated root node
else {
if (root != last) {
root = root.next;
last.next = root;
}
// For a list having a single node
else {
root = last = null;
}
}
}
// displaying the nodes
public void showList() {
listNode temp = root;
if (root == null) {
System.out.println("The list is empty");
} else {
// Traverse the list to show each node's value
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();
// Adds data to the list
list.addValue(1);
list.addValue(2);
list.addValue(3);
list.addValue(4);
list.addValue(8);
list.addValue(10);
// Printing the original list
System.out.println("The initial list is: - ");
list.showList();
// Delete the first node
list.deleteFirstNode();
System.out.println("After deleting the first node, the list is: - ");
list.showList();
// Delete the second node
list.deleteFirstNode();
System.out.println("After deleting the second node, the list is: - ");
list.showList();
}
}
输出
The initial list is: - 1 2 3 4 8 10 After deleting the first node, the list is: - 2 3 4 8 10 After deleting the second node, the list is: - 3 4 8 10
时间复杂度 − O(1)，因为我们在常数时间内修改指针。
空间复杂度 − O(1)，因为我们不使用动态空间。
我们学习了如何从循环链表中删除第一个节点。程序员可以学习如何删除循环链表的最后一个节点。在这种情况下，程序员需要将链表的倒数第二个元素连接到根节点。
145次查看
