Java代码

1. /**
2. * @author luochengcheng
3. * 定义一个单链表
4. */
5. class Node {
6. //变量
7. private int record;
8. //指向下一个对象
9. private Node nextNode;
10.  
11. public Node(int record) {
12. super();
13. this.record = record;
14. }
15. public int getRecord() {
16. return record;
17. }
18. public void setRecord(int record) {
19. this.record = record;
20. }
21. public Node getNextNode() {
22. return nextNode;
23. }
24. public void setNextNode(Node nextNode) {
25. this.nextNode = nextNode;
26. }
27. }
28.  
29. /**
30. * @author luochengcheng
31. * 两种方式实现单链表的反转(递归、普通)
32. * 新手强烈建议旁边拿着纸和笔跟着代码画图(便于理解)
33. */
34. public class ReverseSingleList {
35. /**
36. * 递归，在反转当前节点之前先反转后续节点
37. */
38. public static Node reverse(Node head) {
39. if (null == head || null == head.getNextNode()) {
40. return head;
41. }
42. Node reversedHead = reverse(head.getNextNode());
43. head.getNextNode().setNextNode(head);
44. head.setNextNode(null);
45. return reversedHead;
46. }
47.  
48. /**
49. * 遍历，将当前节点的下一个节点缓存后更改当前节点指针
50. *
51. */
52. public static Node reverse2(Node head) {
53. if (null == head) {
54. return head;
55. }
56. Node pre = head;
57. Node cur = head.getNextNode();
58. Node next;
59. while (null != cur) {
60. next = cur.getNextNode();
61. cur.setNextNode(pre);
62. pre = cur;
63. cur = next;
64. }
65. //将原链表的头节点的下一个节点置为null，再将反转后的头节点赋给head
66. head.setNextNode(null);
67. head = pre;
68.  
69. return head;
70. }
71.  
72. public static void main(String[] args) {
73. Node head = new Node(0);
74. Node tmp = null;
75. Node cur = null;
76. // 构造一个长度为10的链表，保存头节点对象head
77. for (int i = 1; i < 10; i++) {
78. tmp = new Node(i);
79. if (1 == i) {
80. head.setNextNode(tmp);
81. } else {
82. cur.setNextNode(tmp);
83. }
84. cur = tmp;
85. }
86. //打印反转前的链表
87. Node h = head;
88. while (null != h) {
89. System.out.print(h.getRecord() + " ");
90. h = h.getNextNode();
91. }
92. //调用反转方法
93. head = reverse2(head);
94. System.out.println("\n**************************");
95. //打印反转后的结果
96. while (null != head) {
97. System.out.print(head.getRecord() + " ");
98. head = head.getNextNode();
99. }
100. }
101. }