目录
Java 中反向链表的工作原理
1.迭代算法
2.递归算法
Java 中反向链表的示例
示例#2
结论
首页 Java java教程 Java中的反向链表

Java中的反向链表

Aug 30, 2024 pm 03:48 PM
java

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

结论

在本教程中,我们通过定义理解了链表反转的概念,并解释了链表反转的逻辑。讲解了两种反转链表的算法,这是一种迭代算法,并且讲解了递归算法以及用java实现算法的编程示例。

以上是Java中的反向链表的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

突破或从Java 8流返回? 突破或从Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

PHP:网络开发的关键语言 PHP:网络开发的关键语言 Apr 13, 2025 am 12:08 AM

PHP是一种广泛应用于服务器端的脚本语言,特别适合web开发。1.PHP可以嵌入HTML,处理HTTP请求和响应,支持多种数据库。2.PHP用于生成动态网页内容,处理表单数据,访问数据库等,具有强大的社区支持和开源资源。3.PHP是解释型语言,执行过程包括词法分析、语法分析、编译和执行。4.PHP可以与MySQL结合用于用户注册系统等高级应用。5.调试PHP时,可使用error_reporting()和var_dump()等函数。6.优化PHP代码可通过缓存机制、优化数据库查询和使用内置函数。7

PHP与Python:了解差异 PHP与Python:了解差异 Apr 11, 2025 am 12:15 AM

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

Java程序查找胶囊的体积 Java程序查找胶囊的体积 Feb 07, 2025 am 11:37 AM

胶囊是一种三维几何图形,由一个圆柱体和两端各一个半球体组成。胶囊的体积可以通过将圆柱体的体积和两端半球体的体积相加来计算。本教程将讨论如何使用不同的方法在Java中计算给定胶囊的体积。 胶囊体积公式 胶囊体积的公式如下: 胶囊体积 = 圆柱体体积 两个半球体体积 其中, r: 半球体的半径。 h: 圆柱体的高度(不包括半球体)。 例子 1 输入 半径 = 5 单位 高度 = 10 单位 输出 体积 = 1570.8 立方单位 解释 使用公式计算体积: 体积 = π × r2 × h (4

PHP与其他语言:比较 PHP与其他语言:比较 Apr 13, 2025 am 12:19 AM

PHP适合web开发,特别是在快速开发和处理动态内容方面表现出色,但不擅长数据科学和企业级应用。与Python相比,PHP在web开发中更具优势,但在数据科学领域不如Python;与Java相比,PHP在企业级应用中表现较差,但在web开发中更灵活;与JavaScript相比,PHP在后端开发中更简洁,但在前端开发中不如JavaScript。

PHP与Python:核心功能 PHP与Python:核心功能 Apr 13, 2025 am 12:16 AM

PHP和Python各有优势,适合不同场景。1.PHP适用于web开发,提供内置web服务器和丰富函数库。2.Python适合数据科学和机器学习,语法简洁且有强大标准库。选择时应根据项目需求决定。

创造未来:面向零基础的 Java 编程 创造未来:面向零基础的 Java 编程 Oct 13, 2024 pm 01:32 PM

Java是热门编程语言,适合初学者和经验丰富的开发者学习。本教程从基础概念出发,逐步深入讲解高级主题。安装Java开发工具包后,可通过创建简单的“Hello,World!”程序实践编程。理解代码后,使用命令提示符编译并运行程序,控制台上将输出“Hello,World!”。学习Java开启了编程之旅,随着掌握程度加深,可创建更复杂的应用程序。

如何在Spring Tool Suite中运行第一个春季启动应用程序? 如何在Spring Tool Suite中运行第一个春季启动应用程序? Feb 07, 2025 pm 12:11 PM

Spring Boot简化了可靠,可扩展和生产就绪的Java应用的创建,从而彻底改变了Java开发。 它的“惯例惯例”方法(春季生态系统固有的惯例),最小化手动设置

See all articles