Java中的反向链表-java教程-PHP中文网

由节点组成的数据结构，每个节点都有数据和指针，指针指向下一个节点，称为链表，它与数组不同，当这种链表反转时，它是称为反向链表。其中链表分为两部分，称为链表的第一个节点和链表的其余部分，其中链表的其余部分调用反向函数，链表的其余部分链接到第一个节点，头指针固定。在本主题中，我们将学习 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);
}
}

登录后复制

输出：

Java中的反向链表

示例#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中的反向链表