Java雙向鏈表倒置功能實現(xiàn)過程解析
題目要求:Java實現(xiàn)一個雙向鏈表的倒置功能(1->2->3 變成 3->2->1)
提交:代碼、測試用例,希望可以寫成一個Java小項目,可以看到單元測試部分
該題目的代碼,已經(jīng)放到了我的github上,地址為:https://github.com/jiashubing/alibaba-linkedlist-reversed.git
最關鍵的是自定義節(jié)點Node 和自定義雙向鏈表MyLinkedList 兩個類,倒置的方法放在自定義鏈表類里reversed() ,具體的說明都在代碼中
自定義節(jié)點類Node.java,有三個參數(shù) :T data(當前值)、Node<T> left(左節(jié)點)、Node<T> right(右節(jié)點)
自定義雙向鏈表類MyLinkedList.java,有兩個參數(shù):Node<T> head(頭結點)、Node<T> current(當前節(jié)點,也是最后一個節(jié)點)
添加節(jié)點的方法void add(T data):添加的第一個節(jié)點Node,它的左節(jié)點為null,最后一個節(jié)點的右節(jié)點也為null,中間的每個節(jié)點的左右節(jié)點都有值
倒置鏈表的方法reversed():把每個節(jié)點的左右節(jié)點交換,并且把鏈表的首尾節(jié)點也交換,就可以了。這里需要考慮的是循環(huán)的終止條件。我的實現(xiàn)如下:
public void reversed() { if (head == null || head.getRight() == null) { return; } current = head; while(true) { //交換左右節(jié)點 Node<T> tmp = head.getLeft(); head.setLeft(head.getRight()); head.setRight(tmp); //如果左節(jié)點為空,則終止,否則循環(huán)執(zhí)行 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; /** * 自定義節(jié)點 * * @author jiashubing * @since 2018/3/30 */ class Node<T> { /** * 當前值 */ private T data; /** * 左節(jié)點 */ private Node<T> left; /** * 右節(jié)點 */ 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; /** * 當前節(jié)點 */ private Node<T> current; /** * 添加節(jié)點 * 如果頭節(jié)點為空,則賦值為當前節(jié)點 * 否則,要雙向設置,當前節(jié)點向后移動一位 * * @param data 當前節(jié)點的值 */ 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 當前節(jié)點 */ 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 當前節(jié)點 */ 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) { //交換左右節(jié)點 Node<T> tmp = head.getLeft(); head.setLeft(head.getRight()); head.setRight(tmp); //如果左節(jié)點為空,則終止,否則循環(huán)執(zhí)行 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()); } }
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
Java synchronize底層實現(xiàn)原理及優(yōu)化
這篇文章主要介紹了Java synchronize底層實現(xiàn)原理及優(yōu)化,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03SpringBoot時區(qū)問題解決以及徹底解決時差問題
這篇文章主要給大家介紹了關于SpringBoot時區(qū)問題解決以及徹底解決時差問題的相關資料,spring?boot作為微服務簡易架構,擁有其自身的特點,快速搭建架構,簡單快捷,需要的朋友可以參考下2023-08-08Mybatis-Plus3.2.0 MetaObjectHandler 無法進行公共字段全局填充
這篇文章主要介紹了Mybatis-Plus3.2.0 MetaObjectHandler 無法進行公共字段全局填充,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2019-11-11Spring gateway + Oauth2實現(xiàn)單點登錄及詳細配置
gateway是基于 WebFlux的響應式編程框架,所以在使用securityConfig時采用的注解是@EnableWebFluxSecurity,接下來通過本文給大家介紹Spring gateway + Oauth2實現(xiàn)單點登錄及詳細配置,感興趣的朋友一起看看吧2021-09-09