代码示例分析
1 /**
2 * 单链表反转
3 * [1,2,3,4] -> [4,3,2,1]
4 * @author liaowenhui
5 * @date 2021/6/20 16:28
6 */
7 public class testReverseList {
8
9 /**
10 * 方法2 递归反转
11 * 公式含义：把拿到的链表进行反转，然后返回新的头结点。
12 *
13 * @param head
14 * @return
15 */
16 public static ListNode reverseList(ListNode head) {
17 //结束条件
18 if (head == null || head.next == null) {
19 return head;
20 }
21 ListNode newHead = reverseList(head.next);
22 //假设来到递归的最后一步我们已经把 2->3 递归成 3->2，1这个节点还没有去碰它，所以 1 的 next 节点仍然是2，1没有上一个节点。
23 // 让2的next指向 1
24 head.next.next = head;
25 // 1的next指向null.
26 head.next = null;
27 //返回把调整之后的链表
28 return newHead;
29 }
30
31
32 /**
33 * 方法1 迭代
34 * 1->2->3->null
35 * 第一步 1->null 2->3->null
36 * 第二步 2->1->null 3->null
37 * 第三步 3->2->1->null
38 * 最终 3->2->1->null
39 * @param head
40 * @return
41 */
42 public static ListNode reverseList2(ListNode head) {
43 //上一个节点
44 ListNode prev = null;
45 //当前节点
46 ListNode curr = head;
47 while (curr != null) {
48 //原先1的下一个节点是2 原先2的下一个节点是3 原先3的下一个节点是null
49 ListNode next = curr.next;
50
51 //把1的下一个节点置为null 把2的下一个节点置为1 把3的下一个节点置为2
52 curr.next = prev;
53
54 /**
55 * 把当前节点设置为上一个节点
56 * 1为上一个节点 2为上一个节点 3为上一个节点
57 */
58 prev = curr;
59
60 /**
61 * 把原先的下一个节点设置为当前节点
62 * 2为当前节点 3为当前节点 null为下一个节点
63 */
64 curr = next;
65 }
66 return prev;
67 }
68
69 public static void main(String[] args) {
70 //初始化
71 ListNode head = new ListNode(1);
72 ListNode node1 = new ListNode(2);
73 ListNode node2 = new ListNode(3);
74 ListNode node3 = new ListNode(4);
75 head.setNext(node1);
76 node1.setNext(node2);
77 node2.setNext(node3);
78
79 //方法1 迭代
80 //ListNode listNode = reverseList2(head);
81 //方法2 递归反转
82 ListNode listNode = reverseList(head);
83
84 //打印
85 while (null != listNode) {
86 System.out.print(listNode.getDate() + " ");
87 listNode = listNode.getNext();
88 }
89 }
90
91 }
递归理解
递归解题首先要做的是明确递推公式的含义，在这里对于结点1来说，它只需要知道它之后的所有节点反转之后的结果就可以了，也就是说递推公式reverseList的含义是：把拿到的链表进行反转，然后返回新的头结点。
