Java 程序用于反转链接列表而不操作其指针
Java 中的链接列表和指针
链接列表是 Java 环境中的线性数据结构，用于以相邻的方式存储元素。链接列表包含一些地址和指针，用于在列表中存在的元素之间创建链接。链接列表中存在两种类型的元素。它们是 - 数据元素和地址元素。元素的值由数据部分指示，其中地址部分有助于在元素(也称为节点)之间创建链接。
在 Java 中，还有另一个指针的概念。指针是内存中某些特定位置的地址。它们作为对象的引用发挥着重要作用。在本文中，我们将学习如何使用 Java 方法反转链接列表而不操作其指针。
在链接列表的反转操作中，不会对链接进行任何操作。它将链表的节点与前一个节点连接起来。
链表有三个指针 - 当前、上一个和下一个。这些用于使用递归方法到达链接列表的最后一个节点。
实现结果的过程 −
列表划分 - 第一个节点和链接列表。
调用反向
将第一个节点与其余节点链接起来。
头指针为 NULL。
反向链接列表的算法
以下是使用 Java 的反向链接 lint 的一般算法 −
步骤 1 − 类初始化。
步骤 2 − 将头和尾都声明为空。
步骤3 − 分配一个函数来查找链接列表的大小。
步骤 4 − 检查链接列表是否为空。
步骤 5 − 打印数据。
步骤 6 − 声明 temp = temp.next。
步骤 7 − 打印(结束)
步骤 8 − 在开头添加一个节点。
步骤 9 − 声明指向头部的临时节点。
步骤 10 − 判断链接列表是否为空。
步骤 11 − 如果不是，则设置指向 temp 的头部节点。
步骤 12- 在任意索引处添加节点。
步骤 13 - 抛出新异常。
步骤 14 - 返回温度。
步骤 15- int left =0, int right = this.size。
步骤 16 - 交换左右节点的数据。
步骤 17 - 数据反转。
语法
后跟反向链接列表。
While (current!=NULL){
next= current->next;
current->next=prev;
prev=current;
}
*head_ref=prev;
要反转链接列表，有两个最重要的步骤需要遵循；
声明 NULL 指针、head 和 next 指针(其中 prev 和 next 均为 NULL)。
循环遍历链接列表。
以下方法可用于反转没有指针的链接列表 −
方法 1 − 通过改变数据值进行反转
方法 2 − 反转链接列表的迭代方法
通过更改数据值进行反转
无需操纵任何指针，即可反转链接列表。这是通过更改数据的值来实现的。这意味着，在节点中输入新数据以保存并用于进一步的操作。
示例
class LinkedList{
Node head;
class Node{
int data;
Node next;
Node (int x){
data = x;
next = null;
}
}
public void display (){
Node temp = head;
while (temp != null){
System.out.print (temp.data + " ");
temp = temp.next;
}
System.out.println ("END");
}
public Node insertBeginning (int data){
Node newNode = new Node (data);
newNode.next = head;
head = newNode;
return head;
}
public void reverse (){
Node pointer = head;
Node previous = null, current = null;
while (pointer != null){
current = pointer;
pointer = pointer.next;
current.next = previous;
previous = current;
head = current;
}
}
}
public class Main{
public static void main (String[]args){
try{
LinkedList ll0 = new LinkedList ();
ll0.insertBeginning (2);
ll0.insertBeginning (4);
ll0.insertBeginning (6);
ll0.insertBeginning (8);
System.out.println("LinkedList before reversal : ");
ll0.display ();
System.out.println("LinkedList after reversal : ");
ll0.reverse ();
ll0.display ();
}
catch (Exception e){
System.out.println ("Exception occurred.");
}
}
}
输出
LinkedList before reversal : 8 6 4 2 END LinkedList after reversal : 2 4 6 8 END
迭代方法反转链接列表
迭代方法是另一种众所周知的反转链接列表的方法。此方法用于以下程序。
示例
public class LinkedListIterative {
static LinkedListNode head;
static class LinkedListNode {
int val;
LinkedListNode next;
LinkedListNode(int no){
val = no;
next = null;
}
}
LinkedListNode reverse(LinkedListNode node){
LinkedListNode previous = null;
LinkedListNode curr = node;
LinkedListNode next = null;
while (curr != null){
next = curr.next;
curr.next = previous;
previous = curr;
curr = next;
}
node = previous;
return node;
}
void printList(LinkedListNode nde){
while (nde != null){
System.out.print(nde.val + " ");
nde = nde.next;
}
}
public static void main(String argvs[]){
LinkedListIterative listObj = new LinkedListIterative();
listObj.head = new LinkedListNode(4);
listObj.head.next = new LinkedListNode(6);
listObj.head.next.next = new LinkedListNode(7);
listObj.head.next.next.next = new LinkedListNode(1);
listObj.head.next.next.next.next = new LinkedListNode(5);
listObj.head.next.next.next.next.next = new LinkedListNode(8);
listObj.head.next.next.next.next.next.next = new LinkedListNode(3);
listObj.head.next.next.next.next.next.next.next = new LinkedListNode(2);
System.out.println("反转前的链表为:");
listObj.printList(head);
head = listObj.reverse(head);
System.out.println("\n");
System.out.println("反转之后链表为:");
listObj.printList(head);
}
}
输出
反转前的链表为: 4 6 7 1 5 8 3 2 反转之后链表为: 2 3 8 5 1 7 6 4
结论
通过以上讨论，我们了解了如何更改链接列表的数据。同样，我们以同样的方式构建一个 Java 代码，使用列表中名为 left 和 right 的两个指针。
由此可以看出，编写的代码和算法如何帮助您更全面地了解上述方法。
