1 /* 从尾到头递归 */
2 public class JZ6_1
3 {
4 private static ArrayList<Integer> res = new ArrayList<>();
5
6 public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
7 {
8 if (listNode != null)
9 {
10 printListFromTailToHead(listNode.next);
11 res.add(listNode.val);
12 }
13 return res;
14 }
15 }
16
17 /* ArrayList.add(int index, E element) */
18 public class JZ6_2
19 {
20 public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
21 {
22 ArrayList<Integer> res = new ArrayList<>();
23 while (listNode != null)
24 {
25 res.add(0, listNode.val);
26 listNode = listNode.next;
27 }
28 return res;
29 }
30 }
31
32 /* 栈 */
33 public class JZ6_3
34 {
35 public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
36 {
37 ArrayList<Integer> res = new ArrayList<>();
38 Stack<Integer> temp = new Stack<>();
39 while (listNode != null)
40 {
41 temp.add(listNode.val);
42 listNode = listNode.next;
43 }
44 while (!temp.isEmpty())
45 {
46 res.add(temp.pop());
47 }
48 return res;
49 }
50 }
51
52 /* 原地反转链表 */
53 public class JZ6_4
54 {
55 public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
56 {
57 ListNode pre = null, cur = listNode, temp = null;
58 ArrayList<Integer> res = new ArrayList<>();
59 while (cur != null)
60 {
61 temp = cur.next;
62 cur.next = pre;
63 pre = cur;
64 cur = temp;
65 }
66 while (pre != null)
67 {
68 res.add(pre.val);
69 pre = pre.next;
70 }
71 return res;
72 }
73 }
74
75 /* 递归反转链表 */
76 public class JZ6_5
77 {
78 public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
79 {
80 ArrayList<Integer> res = new ArrayList<>();
81
82 ListNode reverseList = reverse(listNode);
83 while (reverseList != null)
84 {
85 res.add(reverseList.val);
86 reverseList = reverseList.next;
87 }
88 return res;
89 }
90
91 public static ListNode reverse(ListNode node)
92 {
93 if (node == null || node.next == null) return node;
94 ListNode fir = node, sec = node.next;
95 fir.next = null;
96 ListNode temp = sec;
97 ListNode reverse = reverse(sec);
98 temp.next = fir;
99 return reverse;
100 }
101 }
1 /* 从尾到头递归 */
2 public class JZ24_1
3 {
4 public static ListNode res, tail;
5
6 public static ListNode ReverseList(ListNode listNode)
7 {
8 if (listNode != null)
9 {
10 ReverseList(listNode.next);
11 if (res == null)
12 res = tail = listNode;
13 else
14 {
15 tail.next = listNode;
16 tail = tail.next;
17 tail.next = null;
18 }
19 }
20 return res;
21 }
22 }
23
24 /* 栈 */
25 public class JZ24_2
26 {
27 public static ListNode ReverseList(ListNode listNode)
28 {
29 ListNode head = new ListNode(-1), tail = head;
30 Stack<Integer> temp = new Stack<>();
31 while (listNode != null)
32 {
33 temp.add(listNode.val);
34 listNode = listNode.next;
35 }
36 while (!temp.isEmpty())
37 {
38 tail.next = new ListNode(temp.pop());
39 tail = tail.next;
40 }
41 return head.next;
42 }
43 }
44
45 /* 原地反转链表 */
46 public class JZ24_3
47 {
48 public static ListNode ReverseList(ListNode listNode)
49 {
50 ListNode pre = null, cur = listNode, temp = null;
51 while (cur != null)
52 {
53 temp = cur.next;
54 cur.next = pre;
55 pre = cur;
56 cur = temp;
57 }
58 return pre;
59 }
60 }
61
62 /* 递归反转链表 */
63 public class JZ24_4
64 {
65 public static ListNode ReverseList(ListNode listNode)
66 {
67 if (listNode == null || listNode.next == null) return listNode;
68 ListNode fir = listNode, sec = listNode.next;
69 fir.next = null;
70 ListNode temp = sec;
71 ListNode reverse = ReverseList(sec);
72 temp.next = fir;
73 return reverse;
74 }
75 }