1.准备链表准备一个由 DataNode 组成的单向链表，DataNode 如下：csharp 代码解读复制代码 public class DataNode {
private int data;private DataNode next;public int getData() { return data;}public void setData(int data) { this.data = data;}public DataNode getNext() { return next;}public void setNext(DataNode next) { this.next = next;}public DataNode(int data) { this.data = data;}
复制代码
}
构造链表 ini 代码解读复制代码 public class DataChain {
private DataNode head;
public DataChain(int size) { DataNode head = new DataNode(0); DataNode cur = head; for (int i = 1; i < size; i++) { DataNode tmp = new DataNode(i); cur.setNext(tmp); cur = tmp; } this.head = head;}
public DataNode getHead() { return head;}
public void setHead(DataNode head) { this.head = head;}
public static void printChain(DataNode head) { StringBuilder sb = new StringBuilder(); DataNode cur = head; sb.append(cur.getData()); while (null != cur.getNext()) { sb.append(" -> "); sb.append(cur.getNext().getData()); cur = cur.getNext(); } System.out.println(sb.toString());}
public static void main(String... strings) { DataChain chain = new DataChain(10); printChain(chain.getHead());}
复制代码
}
运行 main 方法，即构造了一个包含 10 个 node 节点的单链表。rust 代码解读复制代码 #运行结果 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
2.通过递归实现单链表反转考虑到代码的简洁性，首先考虑的是通过递归实现。java 代码解读复制代码 /**
* 递归实现 当栈深度大于12000 则会出现StakOverflowError * * @param head * @return */public static DataNode reverse1(DataNode head) { if (null == head || null == head.getNext()) return head; DataNode revHead = reverse1(head.getNext()); head.getNext().setNext(head); head.setNext(null); return revHead;}
复制代码
以上即是递归实现的源码，但是需要考虑的问题是递归都在 java 栈中进行，需要考虑 jdk 支持的栈的深度。在 jdk1.8.0_91 版本中，当上述链表长度大于 12000 则会出现 StackOverFlowError 错误。说明对于该版本 jdk 栈的深度不能大于 12000。3.通过遍历实现最通用的实现方式就是遍历。ini 代码解读复制代码/**
* 遍历实现 通用实现方法 * * @param head * @return */public static DataNode reverse2(DataNode head) { if (null == head || null == head.getNext()) return head; DataNode pre = head; DataNode cur = head.getNext(); while (null != cur.getNext()) { DataNode tmp = cur.getNext(); cur.setNext(pre); pre = cur; cur = tmp; } cur.setNext(pre); head.setNext(null); return cur;}
复制代码
4.借助 stack 实现考虑到 stack 具有先进后出这一特性，因此可以借助于 stack 数据结构来实现单向链表的反转。ini 代码解读复制代码/**
* 方法3 利用其他数据结构 stack * @param head * @return */public static DataNode reverse3(DataNode head) { Stack<DataNode> stack = new Stack<DataNode>(); for (DataNode node = head; null != node; node = node.getNext()) { stack.add(node); } DataNode reHead = stack.pop(); DataNode cur = reHead; while(!stack.isEmpty()){ cur.setNext(stack.pop()); cur = cur.getNext(); cur.setNext(null); } return reHead;}
复制代码
上述实现方法在于操作简单，对于算法并不精通的同学可以尝试。缺点在于需要通过其他数据结构实现，效率会降低，至于效率会降低到什么程度，后面举例说明。5.三种实现方式效率分析 ini 代码解读复制代码 public static void main(String... strings) {
int size = 10; DataChain chain1 = new DataChain(size); printChain(chain1.getHead()); long reverse1_start = System.currentTimeMillis(); DataNode reNode1 = reverse1(chain1.getHead()); long reverse1_cost = System.currentTimeMillis() - reverse1_start; printChain(reNode1); System.out.println("reverse1 cost time is ["+reverse1_cost+"]ms"); DataChain chain2 = new DataChain(size); printChain(chain2.getHead()); long reverse2_start = System.currentTimeMillis(); DataNode reNode2 = reverse2(chain2.getHead()); long reverse2_cost = System.currentTimeMillis() - reverse2_start; printChain(reNode2); System.out.println("reverse2 cost time is ["+reverse2_cost+"]ms"); DataChain chain3 = new DataChain(size); printChain(chain3.getHead()); long reverse3_start = System.currentTimeMillis(); DataNode reNode3 = reverse3(chain3.getHead()); long reverse3_cost = System.currentTimeMillis() - reverse3_start; printChain(reNode3); System.out.println("reverse3 cost time is ["+reverse3_cost+"]ms");}
复制代码
执行结果：rust 代码解读复制代码 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 99 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0reverse1 cost time is [0]ms0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 99 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0reverse2 cost time is [0]ms0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 99 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0reverse3 cost time is [1]ms
在上述代码基础上，去掉打印输出，将 size 改为 10000，结果如下：css 代码解读复制代码 reverse1 cost time is [1]msreverse2 cost time is [0]msreverse3 cost time is [6]ms
可以看出 reverse2 明显优于其他两种实现方法。考虑到 reverse1 最多只支持 12000，因此将 size 改为 100000 时，再观察 reverse2 和 reverse3 之间的执行结果：css 代码解读复制代码 reverse2 cost time is [6]msreverse3 cost time is [25]ms
因此可以看出，最好的方法是采用遍历的方式进行反转。
行业拓展
近 10 年间，甚至连传统企业都开始大面积数字化时，我们发现开发内部工具的过程中，大量的页面、场景、组件等在不断重复，这种重复造轮子的工作，浪费工程师的大量时间。 针对这类问题，JNPF 低代码平台把某些重复出现的场景、流程，具象化成一个个组件、api、数据库接口，避免了重复造轮子，极大的提高了程序员的生产效率。
体验地址：https://www.jnpfsoft.com
这是一个基于 Flowable 引擎(支持 java、.NET)，已支持 MySQL、SqlServer、Oracle、PostgreSQL、DM（达梦）、 KingbaseES（人大金仓）6 个数据库，支持私有化部署，前后端封装了上千个常用类，方便扩展，框架集成了表单、报表、图表、大屏等各种常用的 Demo 方便直接使用。
至少包含表单建模、流程设计、报表可视化、代码生成器、系统管理、前端 UI 等组件，这种情况下我们避免了重复造轮子，已内置大量的成熟组件，选择合适的组件进行集成或二次开发复杂功能，即可自主开发一个属于自己的应用系统。
评论