服务器之家

服务器之家 > 正文

java 实现单链表逆转详解及实例代码

时间:2020-08-20 11:37     来源/作者:lean1252

java 实现单链表逆转详解

实例代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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];
    }
    /* try {
      Thread.sleep(120000);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }*/
    Node r1 = Node.loopReverse(nodes[0]);
    r1.show();
    Node r = Node.recursionReverse(r1);
    r.show();
 
  } 
}

总结

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

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

原文链接:http://asflex.iteye.com/blog/2084962

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
返回顶部