Java中的反向链表
Aug 30, 2024 pm 03:48 PM
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中文网其他相关文章!
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门文章
击败分裂小说需要多长时间?
3 周前
By DDD
仓库:如何复兴队友
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前
By 尊渡假赌尊渡假赌尊渡假赌
公众号网页更新缓存难题:如何避免版本更新后旧缓存影响用户体验?
3 周前
By 王林

热门文章
击败分裂小说需要多长时间?
3 周前
By DDD
仓库:如何复兴队友
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前
By 尊渡假赌尊渡假赌尊渡假赌
公众号网页更新缓存难题:如何避免版本更新后旧缓存影响用户体验?
3 周前
By 王林

热门文章标签

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)