Java双向链表倒置功能实现过程解析

题目要求：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()); }}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持好吧啦网。