Java中的反向鍊錶

由節點組成的資料結構，每個節點都有資料和指針，指針指向下一個節點，稱為鍊錶，它與數組不同，當這種鍊錶反轉時，它被稱為反向鍊錶。其中鍊錶分為兩部分，稱為鍊錶的第一個節點和鍊錶的其餘部分，其中鍊錶的其餘部分調用反向函數，鍊錶的其餘部分鏈接到第一個節點，頭指針固定。在本主題中，我們將學習 Java 中的反向連結清單。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

Java 中反向鍊錶的工作原理

在java中可以使用兩種演算法來反轉鍊錶。他們是：

1.迭代演算法

以下步驟描述了迭代演算法的工作原理：

• 必須初始化三個指針，分別稱為 ptrA、ptrB 和 ptrC。
• ptrA 先指向。這是ptrA的任務。 ptrB 使用 ptrA 作為指向後面的引用。由於反轉列表中的最後一個節點為空，因此最初，該指標也將為空。
• ptrB 指向第二個位置。這是主要指針。 ptrB 的下一個指向 ptrA，這就是現有指標連結的反轉方式。
• 第三個位置由 ptrC 指向。使用這個指標是為了備份，以確保鍊錶不會在ptrB之前遺失；否則，會導致 ptrB 之前的參考遺失。
• 鍊錶的反轉是從將 ptrA 初始化為 Null 開始的。必須設定為null，因為反轉鍊錶後ptrA將是尾節點。
• ptrB 的下一個連結到 ptrA，因為指向第一個節點的 ptrB 成為反向列表中的尾節點。
• 如果需要反轉只有一個節點的鍊錶，那麼按照上面兩步驟就可以完成任務。
• 當 ptrB 的 next 指向 ptrA 時，對 ptrB 前面的列表的引用將會遺失。因此，在將 ptrB 的下一個指向 ptrA 之前，我們將使用 ptrC 作為 ptrB 的前向清單的備份。
• 重複上述步驟，直到ptrB指向null，這表示所有原始清單節點都被反轉。

2.遞迴演算法

以下步驟描述了遞歸演算法的工作原理：

• 演算法首先考慮目前節點的頭部。
• 如果目前節點為空，則傳回該節點。
• 如果目前節點的下一個元素為空，則表示它是清單中的最後一個節點。反轉列表的頭必須是最後一個節點，因此必須將最後一個節點作為頭然後返回。
• 列表是遞歸遍歷的。
• 目前設定為 current.next.next。
• Null 設定為 current.next。

Java 中反向鍊錶的範例

以下是下面提到的範例

範例#1

使用迭代演算法反轉單鍊錶的 Java 程式

代碼：

class List
{
static Node head1;
static class Node
{
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
//The linked list is reversed using this function
Node reverselist(Node node1)
{
Node previous = null;
Node curr = node1;
Node nex = null;
while (curr != null)
{
nex = curr.nex;
curr.nex = previous;
previous = curr;
curr = nex;
}
node1 = previous;
return node1;
}
// The contents of linked list are printed
void printL(Node node1)
{
while (node1 != null)
{
System.out.print(node1.data1 + " ");
node1 = node1.nex;
}
}
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List l = new List();
l.head1 = new Node(30);
l.head1.nex = new Node(40);
l.head1.nex.nex = new Node(50);
l.head1.nex.nex.nex = new Node(60);
System.out.println("The items in the linked list that needs to be reversed are");
l.printL(head1);
//Function to reverse the list is called here
head1 = l.reverselist(head1);
System.out.println("");
System.out.println("The items in the reversed linked list are");
l.printL(head1);
}
}

輸出：

範例#2

使用迭代演算法反轉單鍊錶的 Java 程式

代碼：

class List {
static Node head1;
static class Node {
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
// A recursive function to reverse the linked list
Node reverse(Node current, Node previous)
{
//Last node is marked as head
if (current.nex == null) {
head1 = current;
//previous node is updated with next
current.nex = previous;
return head1;
}
//current.nex node is saved for the recursive call
Node nex1 = current.nex;
//nex is updated
current.nex = previous;
reverse(nex1, current);
return head1;
}
// Content of the reversed linked list are printed
void printL(Node node)
{
while (node != null) {
System.out.print(node.data1 + " ");
node = node.nex;
}
}
//Main method is called which prints the reversed linked list by calling the function
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List list = new List();
list.head1 = new Node(20);
list.head1.nex = new Node(30);
list.head1.nex.nex = new Node(40);
list.head1.nex.nex.nex = new Node(50);
System.out.println("The items in the linked list that needs to be reversed are");
list.printL(head1);
//Function to reverse the list is called here
Node result = list.reverse(head1, null);
System.out.println("");
System.out.println("");
System.out.println("The items in the reversed linked list are");
list.printL(result);
}
}

輸出：

結論

在本教程中，我們透過定義理解了鍊錶反轉的概念，並解釋了鍊錶反轉的邏輯。講解了兩種反轉鍊錶的演算法，這是一種迭代演算法，並且講解了遞歸演算法以及用java實作演算法的程式設計範例。

以上是Java中的反向鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！