Java实现一个双向链表的倒置功能

 1 <?xml version="1.0" encoding="UTF-8"?>
 2 <project xmlns="http://maven.apache.org/POM/4.0.0"
 3          xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 4          xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
 5     <modelVersion>4.0.0</modelVersion>
 6 
 7     <groupId>cn.jiashubing</groupId>
 8     <artifactId>alitest</artifactId>
 9     <version>1.0-SNAPSHOT</version>
10 
11     <dependencies>
12         <dependency>
13             <groupId>junit</groupId>
14             <artifactId>junit</artifactId>
15             <version>4.12</version>
16         </dependency>
17     </dependencies>
18 
19 </project>

 1 package cn.jiashubing;
 2 
 3 /**
 4  * 自定义节点
 5  *
 6  * @author jiashubing
 7  * @since 2018/3/30
 8  */
 9 class Node<T> {
10 
11     /**
12      * 当前值
13      */
14     private T data;
15 
16     /**
17      * 左节点
18      */
19     private Node<T> left;
20 
21     /**
22      * 右节点
23      */
24     private Node<T> right;
25 
26     Node(T data) {
27         this.data = data;
28         this.left = null;
29         this.right = null;
30     }
31 
32     T getData() {
33         return data;
34     }
35 
36     void setData(T data) {
37         this.data = data;
38     }
39 
40     Node<T> getLeft() {
41         return left;
42     }
43 
44     void setLeft(Node<T> left) {
45         this.left = left;
46     }
47 
48     Node<T> getRight() {
49         return right;
50     }
51 
52     void setRight(Node<T> right) {
53         this.right = right;
54     }
55 }

  1 package cn.jiashubing;
  2 
  3 /**
  4  * 自定义双向链表
  5  *
  6  * @author jiashubing
  7  * @since 2018/3/30
  8  */
  9 public class MyLinkedList<T> {
 10     /**
 11      * 头结点
 12      */
 13     private Node<T> head;
 14 
 15     /**
 16      * 当前节点
 17      */
 18     private Node<T> current;
 19 
 20     /**
 21      * 添加节点
 22      * 如果头节点为空，则赋值为当前节点
 23      * 否则，要双向设置，当前节点向后移动一位
 24      *
 25      * @param data 当前节点的值
 26      */
 27     public void add(T data) {
 28         if (head == null) {
 29             head = new Node<T>(data);
 30             current = head;
 31         } else {
 32             Node<T> tmp = new Node<T>(data);
 33             current.setRight(tmp);
 34             tmp.setLeft(current);
 35             current = current.getRight();
 36         }
 37     }
 38 
 39     /**
 40      * 正向打印链表
 41      *
 42      * @param node 当前节点
 43      */
 44     public void print(Node<T> node) {
 45         if (node == null) {
 46             return;
 47         }
 48 
 49         Node<T> tmp = node;
 50         while (tmp != null) {
 51             System.out.print(tmp.getData() + " ");
 52             tmp = tmp.getRight();
 53         }
 54         System.out.println("");
 55     }
 56 
 57 
 58     /**
 59      * 反向打印链表
 60      *
 61      * @param node 当前节点
 62      */
 63     public void printRev(Node<T> node) {
 64         if (node == null) {
 65             return;
 66         }
 67 
 68         Node<T> tmp = node;
 69         while (tmp != null) {
 70             System.out.print(tmp.getData() + " ");
 71             tmp = tmp.getLeft();
 72         }
 73         System.out.println("");
 74     }
 75 
 76 
 77     /**
 78      * 链表倒置
 79      */
 80     public void reversed() {
 81         if (head == null || head.getRight() == null) {
 82             return;
 83         }
 84         current = head;
 85         while(true) {
 86             //交换左右节点
 87             Node<T> tmp = head.getLeft();
 88             head.setLeft(head.getRight());
 89             head.setRight(tmp);
 90 
 91             //如果左节点为空，则终止，否则循环执行
 92             if (head.getLeft() == null) {
 93                 return;
 94             } else {
 95                 head = head.getLeft();
 96             }
 97         }
 98     }
 99 
100     public Node<T> getHead() {
101         return head;
102     }
103 
104     public Node<T> getCurrent() {
105         return current;
106     }
107 
108 }

 1 import cn.jiashubing.MyLinkedList;
 2 import org.junit.Before;
 3 import org.junit.Test;
 4 
 5 /**
 6  * @author jiashubing
 7  * @since 2018/3/30
 8  */
 9 public class JunitTest {
10 
11     private MyLinkedList<Integer> list;
12 
13     @Before
14     public void setNum() {
15         list = new MyLinkedList<Integer>();
16         for (int i = 1; i < 4; i++) {
17             list.add(i);
18         }
19         System.out.println("正向打印: ");
20         list.print(list.getHead());
21     }
22 
23     @Test
24     public void test1() {
25         System.out.println("链表倒置后正向打印 ");
26         list.reversed();
27         list.print(list.getHead());
28     }
29 
30     @Test
31     public void test2() {
32         System.out.println("逆向打印 ");
33         list.printRev(list.getCurrent());
34     }
35 }