java 实现单链表逆转详解

实例代码：

class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.out.println(); } /** * 递归实现单链表反转,注意：单链表过长，会出现StackOverflowError * @param n * @return */ public static Node recursionReverse(Node n) { long start = System.currentTimeMillis(); if(n == null || n.next == null) { return n; } Node reverseNode = recursionReverse(n.next); n.next.next = n; n.next = null; System.out.println("递归逆置耗时:" + (System.currentTimeMillis() - start) + "ms..."); return reverseNode; } /** * 循环实现单链表反转 * @param n * @return */ public static Node loopReverse(Node n) { long start = System.currentTimeMillis(); if(n == null || n.next == null) { return n; } Node pre = n; Node cur = n.next; Node next = null; while(cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } n.next = null; n = pre; System.out.println("循环逆置耗时:" + (System.currentTimeMillis() - start) + "ms..."); return pre; } @Override public String toString() { return name; } 　　 　　public static void main(String[] args) { int len = 10; Node[] nodes = new Node[len]; for(int i = 0; i < len; i++) { nodes[i] = new Node(i + ""); } for(int i = 0; i < len - 1; i++) { nodes[i].next = nodes[i+1]; } Node r1 = Node.loopReverse(nodes[0]); r1.show(); Node r = Node.recursionReverse(r1); r.show(); }　 }

总结

对于递归和循环，推荐使用循环实现，递归在单链表过大时，会出现StatckOverflowError,递归涉及到方法的调用，在性能上也弱于循环的实现

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！