数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Java 程序删除循环链表的尾节点
在这个 DSA 问题中，我们将学习如何删除循环链表的最后一个节点。
为了从普通链表中删除最后一个节点，我们将第二个节点的 next 指针设置为 Null，但在循环链表中，我们需要将第二个节点的 next 指针设置为根节点。
问题陈述
我们给定一个包含 N 个节点的循环链表。给定的任务是删除链表的最后一个节点。
示例
输入
Hello -> World! -> How -> are -> You -> Doing?
输出
Hello -> World! -> How -> are -> You
解释
我们删除了最后一个节点。
输入
23 -> 4 -> 67 -> 89 -> 73 -> 100
输出
23 -> 4 -> 67 -> 89 -> 73
解释
我们删除了最后一个节点。
方法 1
在这种方法中，我们将找到循环链表的倒数第二个节点。在遍历链表时，我们可以检查当前节点的 next 指针是否指向最后一个节点。如果是，则当前节点是倒数第二个节点，将其 next 指针更新为根节点，并将当前节点设为最后一个节点。
算法
步骤 1 − 定义循环链表节点的 'listNode' 类。还在类中定义字符串数据类型的 'value' 变量和 listNode 类型的 'next' 指针。此外，在构造函数中初始化变量值。
步骤 2 − 定义 'root' 和 'last' 指针。
步骤 3 − 创建 addNode() 函数以将节点添加到循环链表中。
步骤 3.1 − 在 addNode() 函数中，使用给定值初始化新节点。
步骤 3.2 − 如果 root 指针为 null，则将根节点和最后一个节点更新为 null。此外，将新节点的 next 指针更新为 root 指针。
步骤 3.3 − 在其他情况下，将最后一个节点与新节点连接，将新节点设为最后一个节点，并将更新后的最后一个节点连接到根节点。
步骤 4 − 创建 deleteLastNode() 函数以从链表中删除最后一个节点。
步骤 4.1 − 对于空列表，执行 return 语句。
步骤 4.2 − 当根节点和最后一个节点不相等时，遍历链表，直到当前节点的 next 指针指向最后一个节点。
步骤 4.3 − 之后，将倒数第二个节点设为最后一个节点，并将其与根节点连接。
步骤 4.4 − 当根节点和最后一个节点相等时，将根节点和最后一个节点更新为 null。
步骤 5 − 创建 printList() 函数以打印链表的元素。
步骤 5.1 − 使用 do-while 循环遍历列表，直到 'temp' 节点等于 'root' 节点，并打印每个节点的值。
步骤 6 − 多次执行 addNode() 方法以将多个节点添加到循环链表中。
步骤 7 − 使用 printList() 方法打印初始列表。现在，执行 deleteLastNode() 函数以删除最后一个节点，并使用 printList() 方法显示更新后的列表。
示例
public class Main {
// Node for creating the linked list
public class listNode {
String value;
listNode next;
public listNode(String val) {
this.value = val;
}
}
// Root and last node initialization
public listNode root = null;
public listNode last = null;
// Method to add new Node
public void addNode(String 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 deleteLastNode() {
// 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) {
listNode temp = root;
while (temp.next != last) {
temp = temp.next;
}
// Second last element is the new tail
last = temp;
last.next = root;
}
// For a list having a single node
else {
root = last = null;
}
}
}
// displaying the nodes
public void printList() {
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.addNode("Hello");
list.addNode("World!");
list.addNode("How");
list.addNode("are");
list.addNode("You");
list.addNode("Doing?");
// Printing the original list
System.out.println("The initial list is :- ");
list.printList();
// Delete the first node
list.deleteLastNode();
System.out.println("After deleting the first node, the list is :- ");
list.printList();
// Delete the second node
list.deleteLastNode();
System.out.println("After deleting the second node, the list is :- ");
list.printList();
}
}
输出
The initial list is :- Hello World! How are You Doing? After deleting the first node, the list is :- Hello World! How are You After deleting the second node, the list is :- Hello World! How are
时间复杂度 − O(N)，因为我们需要到达最后一个节点。
空间复杂度 − O(1)，因为我们没有使用任何额外的空间。
从循环链表中删除最后一个节点的逻辑部分是找到倒数第二个节点并将其与根节点连接。程序员可以尝试删除循环链表的第一个节点以进行更多练习。
116 次查看
