資料結構
網路
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次檢視
