JAVA|java-单链表反转解法及分析


文章目录

  • 1.准备链表
  • 2.通过递归实现单链表反转
  • 3.通过遍历实现
  • 4.借助stack实现
  • 5.三种实现方式效率分析

最近与人瞎聊,聊到各大厂的面试题,其中有一个就是用java实现单链表反转。闲来无事,决定就这个问题进行一番尝试。
1.准备链表 准备一个由DataNode组成的单向链表,DataNode如下:
public class DataNode { private int data; private DataNode next; public int getData() { return data; } public void setData(int data) { this.data = https://www.it610.com/article/data; } public DataNode getNext() { return next; } public void setNext(DataNode next) { this.next = next; } public DataNode(int data) { this.data = data; } }

构造链表
public class DataChain { privateDataNode 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节点的单链表。
#运行结果 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

2.通过递归实现单链表反转 考虑到代码的简洁性,首先考虑的是通过递归实现。
/** * 递归实现 当栈深度大于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.通过遍历实现 最通用的实现方式就是遍历。
/** * 遍历实现 通用实现方法 * * @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数据结构来实现单向链表的反转。
/** * 方法3 利用其他数据结构 stack * @param head * @return */ public static DataNode reverse3(DataNode head) { Stack stack = new Stack(); 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.三种实现方式效率分析
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"); }

执行结果:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 reverse1 cost time is [0]ms 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 reverse2 cost time is [0]ms 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 reverse3 cost time is [1]ms

在上述代码基础上,去掉打印输出,将size改为10000,结果如下:
reverse1 cost time is [1]ms reverse2 cost time is [0]ms reverse3 cost time is [6]ms

可以看出reverse2 明显优于其他两种实现方法。考虑到reverse1最多只支持12000,因此将size改为100000时,再观察reverse2和reverse3之间的执行结果:
reverse2 cost time is [6]ms reverse3 cost time is [25]ms

【JAVA|java-单链表反转解法及分析】因此可以看出,最好的方法是采用遍历的方式进行反转。

    推荐阅读