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

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 left（左节点）、Node right（右节点）

自定义双向链表类MyLinkedList.java，有两个参数：Node head（头结点）、Node current（当前节点，也是最后一个节点）

添加节点的方法void add(T data)：添加的第一个节点Node，它的左节点为null，最后一个节点的右节点也为null，中间的每个节点的左右节点都有值

倒置链表的方法reversed()：把每个节点的左右节点交换，并且把链表的首尾节点也交换，就可以了。这里需要考虑的是循环的终止条件。我的实现如下：

public void reversed() {

　　if (head == null || head.getRight() == null) {

　　　　return;

　　}

　　current = head;

　　while(true) {

　　　　//交换左右节点

　　　　Node tmp = head.getLeft();

　　　　head.setLeft(head.getRight());

　　　　head.setRight(tmp);

　　　　//如果左节点为空，则终止，否则循环执行

　　　　if (head.getLeft() == null) {

　　　　　　return;

　　　　} else {

　　　　　　head = head.getLeft();

　　　　}

　　}

}

剩下的测试用例，就简单了。下面是我的github上的代码，记录下：

pom.xml

xmlns:xsi="http://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">

4.0.0

cn.jiashubing

alitest

1.0-SNAPSHOT

junit

junit

4.12

xmlns:xsi="http://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">

4.0.0

cn.jiashubing

alitest

1.0-SNAPSHOT

junit

junit

4.12

Node.java

package cn.jiashubing;

/**

* 自定义节点

*

* @author jiashubing

* @since 2018/3/30

*/

class Node {

/**

* 当前值

*/

private T data;

/**

* 左节点

*/

private Node left;

/**

* 右节点

*/

private Node 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 getLeft() {

return left;

}

void setLeft(Node left) {

this.left = left;

}

Node getRight() {

return right;

}

void setRight(Node right) {

this.right = right;

}

}

MyLinkedList.java

package cn.jiashubing;

/**

* 自定义双向链表

*

* @author jiashubing

* @since 2018/3/30

*/

public class MyLinkedList {

/**

* 头结点

*/

private Node head;

/**

* 当前节点

*/

private Node current;

/**

* 添加节点

* 如果头节点为空，则赋值为当前节点

* 否则，要双向设置，当前节点向后移动一位

*

* @param data 当前节点的值

*/

public void add(T data) {

if (head == null) {

head = new Node(data);

current = head;

} else {

Node tmp = new Node(data);

current.setRight(tmp);

tmp.setLeft(current);

current = current.getRight();

}

}

/**

* 正向打印链表

*

* @param node 当前节点

*/

public void print(Node node) {

if (node == null) {

return;

}

Node tmp = node;

while (tmp != null) {

Systehttp://m.out.print(tmp.getData() + " ");

tmp = tmp.getRight();

}

System.out.println("");

}

/**

* 反向打印链表

*

* @param node 当前节点

*/

public void printRev(Node node) {

if (node == null) {

return;

}

Node 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 tmp = head.getLeft();

head.setLeft(head.getRight());

head.setRight(tmp);

//如果左节点为空，则终止，否则循环执行

if (head.getLeft() == null) {

return;

} else {

head = head.getLeft();

}

}

}

public Node getHead() {

return head;

}

public Node 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 list;

@Before

public void setNum() {

list = new MyLinkedList();

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());

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。