資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Java程式：刪除迴圈連結串列中間節點
在這個資料結構與演算法(DSA)問題中，我們將學習如何刪除迴圈連結串列中的中間節點。
刪除迴圈連結串列中的中間節點與刪除普通連結串列中的中間節點方法類似。我們需要找到中間節點的前一個和後一個節點，並將它們直接連線起來以刪除中間節點。
問題陳述
我們有一個迴圈連結串列，需要刪除連結串列中的中間節點。如果連結串列包含偶數個節點，則第(N/2)個節點是中間節點。
示例
輸入
90 32 67 84 23 78
輸出
90 32 84 23 78
解釋
67被刪除，因為它是一箇中間節點。
輸入
90 32 84 23 78
輸出
90 32 23 78
解釋
84被刪除，因為它是一箇中間節點。
方法一
首先需要計算連結串列中節點的總數。如果節點總數為偶數，則刪除第(N/2)個節點。否則，如果節點總數為奇數，則中間節點為(N/2)+1個節點。
我們需要找到中間節點的前一個節點，並將其下一個指標的值更新為中間節點的下一個指標的值，從而刪除中間節點。
演算法
步驟1 - 定義名為'dataNode'的類，其中包含整數型別的'val'變數和'dataNode'型別的next指標。
步驟2 - 定義名為'listSize'的靜態變數來儲存連結串列的大小。同時，定義'root'和'end'指標來儲存第一個和最後一個節點。
步驟3 - 接下來，定義該類的建構函式來初始化'root'和'end'節點，並將列表的大小初始化為0。
步驟4 - 定義addToList()函式向迴圈連結串列新增節點。
步驟4.1 - 在addToList()函式中，使用給定值定義'newNode'型別的dataNode。
步驟4.2 - 如果root節點為空，則使用newNode更新root和end節點。同時，將newNode的next指標指向root節點。
步驟4.3 - 否則，將最後一個節點的next指標指向newNode。同時，更新'end'指標的值，並將最後一個節點的next指標指向'root'節點。
步驟4.4 - 新增節點後，將'listSize'加1。
步驟5 - 定義middleDeletion()函式來刪除中間節點。
步驟5.1 - 如果'listSize'是偶數，則將mid初始化為'listSize/2'。否則，將mid初始化為(listSize/2) + 1。
步驟5.2 - 如果root為空，則執行返回。
步驟5.3 - 如果root和end相等，則將root和end指標更新為空。
步驟5.4 - 如果mid等於1，則將root節點更新為end節點，並將end節點的next指標更新為end。
步驟5.5 - 在其他情況下，將'curr'初始化為root節點，'previous'初始化為空，p初始化為1。
步驟5.6 - 使用迴圈進行迭代，直到p小於mid。在迴圈中，將previous更新為'curr'，'curr'更新為其下一個節點，並將p的值加1。
步驟5.7 - 之後，將'previous'節點的next指標更新為'curr'節點的next指標。同時，將'curr'設定為null，並將listSize減1。
步驟6 - 定義showList()函式來列印列表。
步驟6.1 - 在函式中，使用do-while迴圈遍歷列表，並列印每個節點的值。
步驟7 - 現在，使用addToList()方法向連結串列新增節點。
步驟8 - 使用middleDeletion()函式刪除中間元素，並使用showList()函式列印更新後的列表的元素。
示例
public class Main {
class dataNode {
int val;
dataNode next;
}
private static int listSize;
private dataNode root, end;
// Class constructor
Main() {
this.root = null;
this.end = null;
listSize = 0;
}
public void addToList(int val) {
// New node creation
dataNode newNode = new dataNode();
// For empty list
if (this.root == null) {
newNode.val = val;
this.root = newNode;
this.end = newNode;
newNode.next = this.root;
}
// Append new node at last of the list. connect end node with the root node
else {
newNode.val = val;
end.next = newNode;
end = newNode;
end.next = root;
}
listSize++;
}
public void middleDeletion() {
int mid;
dataNode curr, previous;
// Middle position calculation
if (listSize % 2 == 0) {
mid = listSize / 2;
} else {
mid = (listSize / 2) + 1;
}
// For an empty list
if (root == null) {
return;
}
// For a list having a single node
else if (root == end) {
root = null;
end = null;
}
// For list having two nodes
else if (mid == 1) {
root = end;
end.next = end;
}
// For a list having three or more nodes
else {
curr = root;
previous = null;
int p = 1;
// Reach to the middle node
while (p < mid) {
previous = curr;
curr = curr.next;
p++;
}
// Join the previous node with next node of middle
previous.next = curr.next;
curr = null;
}
listSize--;
if (listSize < 0) {
listSize = 0;
}
}
public void showList() {
// For an empty list
if (root == null) {
System.out.println("The list is empty");
} else {
dataNode curr = root;
// Traverse the linked list
do {
System.out.print(curr.val + " ");
curr = curr.next;
} while (curr != root);
System.out.println();
}
}
public static void main(String args[]) {
Main obj = new Main();
// Add nodes
obj.addToList(90);
obj.addToList(32);
obj.addToList(67);
obj.addToList(84);
obj.addToList(23);
obj.addToList(78);
System.out.print("Initial list is: ");
obj.showList();
// Middle node deletion
obj.middleDeletion();
System.out.print("The updated list after deleting the middle node is: ");
obj.showList();
// Middle node deletion
obj.middleDeletion();
System.out.print("The updated list after deleting the middle node is: ");
obj.showList();
}
}
輸出
Initial list is: 90 32 67 84 23 78 The updated list after deleting the middle node is: 90 32 84 23 78 The updated list after deleting the middle node is: 90 32 23 78
時間複雜度 - O(N) 用於查詢中間元素。
空間複雜度 - O(1)，因為我們使用了常量空間。
邏輯部分是找到中間節點的前一個和後一個節點，並將它們連線起來以刪除中間節點。程式設計師也可以練習從迴圈連結串列中刪除起始或結束節點。
瀏覽量：134
