`
Poly
  • 浏览: 34375 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Java反转单链表(code)

阅读更多

主要是面试中可能会经常碰上该类似操作,尤其是稍大点公司,面试官可能并不在乎你能不能搞定该题,但是这类型题目最是能体现程序员的思维状态 ---一个迷糊头脑的程序员 怎能立志改变这个世界

 

/**
 * @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();
		}
	}
}

 

分享到:
评论
3 楼 somefuture 2016-08-03  
反转的时候多了三个节点空间,能用更少的实现吗
2 楼 353144988 2015-12-24  
1 楼 353144988 2015-12-24  

相关推荐

    Java实现单链表以及单链表的操作.zip

    本教程将深入探讨如何使用Java语言来实现单链表及其相关操作。 首先,我们来理解单链表的基本概念。单链表由一系列节点组成,每个节点包含两部分:数据域(用于存储数据)和指针域(指向下一个节点)。链表的最后一...

    两种方法反转单链表

    本文将深入探讨两种方法来反转单链表,这些方法是基于Java编程语言实现的,因此相关知识点包括链表操作、递归以及迭代。 首先,我们需要了解单链表的基本结构。在Java中,一个简单的单链表节点可以定义为: ```...

    基于JAVA的单链表简单实现

    在Java中,我们可以使用对象和引用的概念来实现单链表。 首先,我们需要创建一个表示链表节点的类Node,它通常有两个属性:data(用于存储数据)和next(用于存储指向下一个节点的引用)。例如: ```java public ...

    C++ 单链表反转 C++ 单链表反转

    单链表反转是一个常见的操作,它将链表中的节点顺序颠倒。给定的代码实现了一个函数`Reverse`来完成这个任务。下面我们将详细讨论这个反转过程。 首先,我们需要检查输入的链表头是否为空。如果为空,则无需反转,...

    链表-基于Java的单链表基本操作之链表反转.zip

    链表 链表_基于Java的单链表基本操作之链表反转

    java实现单链表

    在这个主题中,我们将深入探讨如何使用Java来实现单链表,特别是关注如何插入元素以及如何构建链表。 单链表由一系列节点组成,每个节点包含两部分:数据元素和指向下一个节点的引用。在Java中,我们可以通过创建一...

    单链表的就地反转

    单链表的就地反转 单链表的就地反转是指在不使用额外的存储空间的情况下,反转单链表的节点顺序。该操作对链表的结构进行了重新组织,使得链表的节点顺序被反转。 在该实验报告中,我们将学习如何使用C语言来实现...

    Python3实现的反转单链表算法示例

    反转单链表是常见的链表操作之一,它将链表中的顺序颠倒,例如原本的1-&gt;2-&gt;3-&gt;4反转后变为4-&gt;3-&gt;2-&gt;1。本文将深入探讨如何使用Python3实现这个操作,包括迭代和递归两种方法。 ### 方案一:迭代 迭代方法是通过...

    单链表反转

    单链表反转是面试时经常会遇到的问题,之前只是在数据结构里用伪代码实现过单链表反转。为落实亲手编写每一个程序的目标,在这里用java实现反转。方法有很多,这里只写最优的。时间复杂度O(n),空间复杂度O(1)。也...

    java 转义和反转义工具类 java 转义和反转义工具类

    java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和...

    我的Java单链表练习

    本文以“我的Java单链表练习”为主题,通过博主baby69yy2000在iteye上的博客分享,深入探讨了Java中实现单链表的相关知识。 首先,我们要理解单链表的概念。单链表是一种线性数据结构,由一系列节点(也称为元素或...

    反转单链表

    让一个单链表反转,就是头当做尾,尾做头,各个结点的指向反向

    Java单链表增删改查的实现

    下面我们将详细探讨如何在Java中实现单链表的增、删、改、查功能,以及如何进行选择排序、冒泡排序和反转排序。 1. **单链表的定义**: - 单链表的每个节点通常包括两部分:数据域(存储元素)和指针域(存储下一...

    java 实现单链表逆转详解及实例代码

    在这个Java实现中,我们有两个方法来完成这个任务:一个使用递归,另一个使用循环。 1. **递归实现单链表逆转**: 递归方法通过将问题分解为更小的子问题来工作。在这里,我们首先检查基本情况,即链表为空或只有...

    单链表反转 链表相交

    实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....

    Java算法实例-单链表操作

    在这个"Java算法实例-单链表操作"中,我们将探讨如何在Java中实现单链表,包括其基本操作如插入、删除、遍历等。这些操作对于理解和解决各种算法问题至关重要,尤其对于学习和准备编程考试的学员来说,是非常实用的...

    Java算法篇-单链表反转详解.pptx.pptx

    在Java中,单链表反转的代码实现可以采用迭代或递归的方式。迭代方法通常涉及三个指针,分别用于追踪当前节点、前一个节点和头节点。在遍历过程中,当前节点的next指针会指向前一个节点,然后前一个节点和当前节点...

    java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类

    java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转义工具类java 转义和反转...

    Java实现单链表翻转实例代码

    在Java编程中,单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个值和一个指向下一个节点的引用。单链表的翻转是数据结构与算法中的一个经典问题,通常有两种主要的实现方式:递归和非递归。本篇...

    基于Java实现的单链表基本操作之链表反转.zip

    在这个基于Java实现的单链表基本操作中,我们将重点关注链表反转这一特定操作。 链表反转是编程面试中常见的问题,它要求我们改变链表中节点的顺序,使得原链表的最后一个节点成为新链表的第一个节点,原链表的第一...

Global site tag (gtag.js) - Google Analytics