資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
