主要是面试中可能会经常碰上该类似操作,尤其是稍大点公司,面试官可能并不在乎你能不能搞定该题,但是这类型题目最是能体现程序员的思维状态 ---一个迷糊头脑的程序员 怎能立志改变这个世界
/**
* @author luochengcheng
* 定义一个单链表
*/
class Node {
//变量
private int record;
//指向下一个对象
private Node nextNode;
public Node(int record) {
super();
this.record = record;
}
public int getRecord() {
return record;
}
public void setRecord(int record) {
this.record = record;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
}
/**
* @author luochengcheng
* 两种方式实现单链表的反转(递归、普通)
* 新手强烈建议旁边拿着纸和笔跟着代码画图(便于理解)
*/
public class ReverseSingleList {
/**
* 递归,在反转当前节点之前先反转后续节点
*/
public static Node reverse(Node head) {
if (null == head || null == head.getNextNode()) {
return head;
}
Node reversedHead = reverse(head.getNextNode());
head.getNextNode().setNextNode(head);
head.setNextNode(null);
return reversedHead;
}
/**
* 遍历,将当前节点的下一个节点缓存后更改当前节点指针
*
*/
public static Node reverse2(Node head) {
if (null == head) {
return head;
}
Node pre = head;
Node cur = head.getNextNode();
Node next;
while (null != cur) {
next = cur.getNextNode();
cur.setNextNode(pre);
pre = cur;
cur = next;
}
//将原链表的头节点的下一个节点置为null,再将反转后的头节点赋给head
head.setNextNode(null);
head = pre;
return head;
}
public static void main(String[] args) {
Node head = new Node(0);
Node tmp = null;
Node cur = null;
// 构造一个长度为10的链表,保存头节点对象head
for (int i = 1; i < 10; i++) {
tmp = new Node(i);
if (1 == i) {
head.setNextNode(tmp);
} else {
cur.setNextNode(tmp);
}
cur = tmp;
}
//打印反转前的链表
Node h = head;
while (null != h) {
System.out.print(h.getRecord() + " ");
h = h.getNextNode();
}
//调用反转方法
head = reverse2(head);
System.out.println("\n**************************");
//打印反转后的结果
while (null != head) {
System.out.print(head.getRecord() + " ");
head = head.getNextNode();
}
}
}
分享到:
相关推荐
本教程将深入探讨如何使用Java语言来实现单链表及其相关操作。 首先,我们来理解单链表的基本概念。单链表由一系列节点组成,每个节点包含两部分:数据域(用于存储数据)和指针域(指向下一个节点)。链表的最后一...
本文将深入探讨两种方法来反转单链表,这些方法是基于Java编程语言实现的,因此相关知识点包括链表操作、递归以及迭代。 首先,我们需要了解单链表的基本结构。在Java中,一个简单的单链表节点可以定义为: ```...
在Java中,我们可以使用对象和引用的概念来实现单链表。 首先,我们需要创建一个表示链表节点的类Node,它通常有两个属性:data(用于存储数据)和next(用于存储指向下一个节点的引用)。例如: ```java public ...
单链表反转是一个常见的操作,它将链表中的节点顺序颠倒。给定的代码实现了一个函数`Reverse`来完成这个任务。下面我们将详细讨论这个反转过程。 首先,我们需要检查输入的链表头是否为空。如果为空,则无需反转,...
链表 链表_基于Java的单链表基本操作之链表反转
在这个主题中,我们将深入探讨如何使用Java来实现单链表,特别是关注如何插入元素以及如何构建链表。 单链表由一系列节点组成,每个节点包含两部分:数据元素和指向下一个节点的引用。在Java中,我们可以通过创建一...
单链表的就地反转 单链表的就地反转是指在不使用额外的存储空间的情况下,反转单链表的节点顺序。该操作对链表的结构进行了重新组织,使得链表的节点顺序被反转。 在该实验报告中,我们将学习如何使用C语言来实现...
反转单链表是常见的链表操作之一,它将链表中的顺序颠倒,例如原本的1->2->3->4反转后变为4->3->2->1。本文将深入探讨如何使用Python3实现这个操作,包括迭代和递归两种方法。 ### 方案一:迭代 迭代方法是通过...
单链表反转是面试时经常会遇到的问题,之前只是在数据结构里用伪代码实现过单链表反转。为落实亲手编写每一个程序的目标,在这里用java实现反转。方法有很多,这里只写最优的。时间复杂度O(n),空间复杂度O(1)。也...
java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和...
本文以“我的Java单链表练习”为主题,通过博主baby69yy2000在iteye上的博客分享,深入探讨了Java中实现单链表的相关知识。 首先,我们要理解单链表的概念。单链表是一种线性数据结构,由一系列节点(也称为元素或...
让一个单链表反转,就是头当做尾,尾做头,各个结点的指向反向
下面我们将详细探讨如何在Java中实现单链表的增、删、改、查功能,以及如何进行选择排序、冒泡排序和反转排序。 1. **单链表的定义**: - 单链表的每个节点通常包括两部分:数据域(存储元素)和指针域(存储下一...
在这个Java实现中,我们有两个方法来完成这个任务:一个使用递归,另一个使用循环。 1. **递归实现单链表逆转**: 递归方法通过将问题分解为更小的子问题来工作。在这里,我们首先检查基本情况,即链表为空或只有...
实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....
在这个"Java算法实例-单链表操作"中,我们将探讨如何在Java中实现单链表,包括其基本操作如插入、删除、遍历等。这些操作对于理解和解决各种算法问题至关重要,尤其对于学习和准备编程考试的学员来说,是非常实用的...
在Java中,单链表反转的代码实现可以采用迭代或递归的方式。迭代方法通常涉及三个指针,分别用于追踪当前节点、前一个节点和头节点。在遍历过程中,当前节点的next指针会指向前一个节点,然后前一个节点和当前节点...
java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转...
在Java编程中,单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个值和一个指向下一个节点的引用。单链表的翻转是数据结构与算法中的一个经典问题,通常有两种主要的实现方式:递归和非递归。本篇...
在这个基于Java实现的单链表基本操作中,我们将重点关注链表反转这一特定操作。 链表反转是编程面试中常见的问题,它要求我们改变链表中节点的顺序,使得原链表的最后一个节点成为新链表的第一个节点,原链表的第一...