题目要求：Java实现一个双向链表的倒置功能（1->2->3 变成 3->2->1)
提交：代码、测试用例，希望可以写成一个Java小项目，可以看到单元测试部分
该题目的代码，已经放到了我的github上，地址为：https://github.com/jiashubing/alibaba-linkedlist-reversed.git
最关键的是自定义节点Node 和自定义双向链表MyLinkedList 两个类，倒置的方法放在自定义链表类里reversed() ，具体的说明都在代码中
自定义节点类Node.java，有三个参数 ：T data（当前值）、Node<T> left（左节点）、Node<T> right（右节点）
自定义双向链表类MyLinkedList.java，有两个参数：Node<T> head（头结点）、Node<T> current（当前节点，也是最后一个节点）
添加节点的方法void add(T data)：添加的第一个节点Node，它的左节点为null，最后一个节点的右节点也为null，中间的每个节点的左右节点都有值
倒置链表的方法reversed()：把每个节点的左右节点交换，并且把链表的首尾节点也交换，就可以了。这里需要考虑的是循环的终止条件。我的实现如下：
public void reversed() {
if (head == null || head.getRight() == null) {
return;
}
current = head;
while(true) {
//交换左右节点
Node<T> tmp = head.getLeft();
head.setLeft(head.getRight());
head.setRight(tmp);
//如果左节点为空，则终止，否则循环执行
if (head.getLeft() == null) {
return;
} else {
head = head.getLeft();
}
}
}
剩下的测试用例，就简单了。下面是我的github上的代码，记录下：
pom.xml
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>cn.jiashubing</groupId>
<artifactId>alitest</artifactId>
<version>1.0-SNAPSHOT</version>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.12</version>
</dependency>
</dependencies>
</project>
Node.java
package cn.jiashubing;
/**
* 自定义节点
*
* @author jiashubing
* @since 2018/3/30
*/
class Node<T> {
/**
* 当前值
*/
private T data;
/**
* 左节点
*/
private Node<T> left;
/**
* 右节点
*/
private Node<T> right;
Node(T data) {
this.data = data;
this.left = null;
this.right = null;
}
T getData() {
return data;
}
void setData(T data) {
this.data = data;
}
Node<T> getLeft() {
return left;
}
void setLeft(Node<T> left) {
this.left = left;
}
Node<T> getRight() {
return right;
}
void setRight(Node<T> right) {
this.right = right;
}
}
MyLinkedList.java
package cn.jiashubing;
/**
* 自定义双向链表
*
* @author jiashubing
* @since 2018/3/30
*/
public class MyLinkedList<T> {
/**
* 头结点
*/
private Node<T> head;
/**
* 当前节点
*/
private Node<T> current;
/**
* 添加节点
* 如果头节点为空，则赋值为当前节点
* 否则，要双向设置，当前节点向后移动一位
*
* @param data 当前节点的值
*/
public void add(T data) {
if (head == null) {
head = new Node<T>(data);
current = head;
} else {
Node<T> tmp = new Node<T>(data);
current.setRight(tmp);
tmp.setLeft(current);
current = current.getRight();
}
}
/**
* 正向打印链表
*
* @param node 当前节点
*/
public void print(Node<T> node) {
if (node == null) {
return;
}
Node<T> tmp = node;
while (tmp != null) {
System.out.print(tmp.getData() + " ");
tmp = tmp.getRight();
}
System.out.println("");
}
/**
* 反向打印链表
*
* @param node 当前节点
*/
public void printRev(Node<T> node) {
if (node == null) {
return;
}
Node<T> tmp = node;
while (tmp != null) {
System.out.print(tmp.getData() + " ");
tmp = tmp.getLeft();
}
System.out.println("");
}
/**
* 链表倒置
*/
public void reversed() {
if (head == null || head.getRight() == null) {
return;
}
current = head;
while(true) {
//交换左右节点
Node<T> tmp = head.getLeft();
head.setLeft(head.getRight());
head.setRight(tmp);
//如果左节点为空，则终止，否则循环执行
if (head.getLeft() == null) {
return;
} else {
head = head.getLeft();
}
}
}
public Node<T> getHead() {
return head;
}
public Node<T> getCurrent() {
return current;
}
}
JunitTest.java
import cn.jiashubing.MyLinkedList;
import org.junit.Before;
import org.junit.Test;
/**
* @author jiashubing
* @since 2018/3/30
*/
public class JunitTest {
private MyLinkedList<Integer> list;
@Before
public void setNum() {
list = new MyLinkedList<Integer>();
for (int i = 1; i < 4; i++) {
list.add(i);
}
System.out.println("正向打印: ");
list.print(list.getHead());
}
@Test
public void test1() {
System.out.println("链表倒置后正向打印 ");
list.reversed();
list.print(list.getHead());
}
@Test
public void test2() {
System.out.println("逆向打印 ");
list.printRev(list.getCurrent());
}
}
原文链接：https://www.cnblogs.com/acm-bingzi/p/alibaba-linkedlist-reversed.html
作者：贾树丙
