从尾到头打印链表
蠢想法
解题思路
的节点顺序已经反转过来了
栈
package swordPointingToTheOffer;
import java.util.Stack; //引用栈
public class six {
//初始化
Stack<Integer> stack = new Stack<Integer>();
//进栈
public void push(int node){
stack.push(node);
}
//出栈
public int pop(){
return stack.pop();
}
// //取栈顶值(不出栈)
// stack.peek();
// //判断栈是否为空
// stack.isEmpty()
/**
* 链表节点
*/
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public int[] reversePrint(ListNode head) {
ListNode node = head;
Stack<Integer> st = new Stack<Integer>();
while (node != null) {
//压栈
st.push(node.val);
//链表指针后移
node = node.next;
}
int i = 0;
//弹栈到数组里面
int[] res = new int[st.size()];
while (i < res.length) {
res[i++] = st.pop();
}
return res;
}
public static void main(String[] args) {
//构建链表 (1->3->2)
ListNode head = new ListNode(1);
head.next = new ListNode(3);
head.next.next = new ListNode(2);
six sol = new six();
//反转
int[] res = sol.reversePrint(head);
for (int x : res) {
System.out.println(x);
}
}
}
将Stack中的元素pop出来存入数组int[]
递归隐式使用栈
package swordPointingToTheOffer;
import java.util.ArrayList;
import java.util.Stack; //引用栈
public class six {
/**
* 链表节点
*/
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
//数组,用于存放弹栈的资源。。。
ArrayList<Integer> tmp = new ArrayList<Integer>();
public int[] reversePrint2(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for (int i = 0; i < tmp.size(); i++) {
res[i] = tmp.get(i);
}
return res;
}
void recur(ListNode head) {
if (head == null) {
return;
}
recur(head.next);
//弹栈到数组里面
tmp.add(head.val);
}
public static void main(String[] args) {
//构建链表 (1->3->2)
ListNode head = new ListNode(1);
head.next = new ListNode(3);
head.next.next = new ListNode(2);
six sol = new six();
//反转
int[] res = sol.reversePrint2(head);
for (int x : res) {
System.out.println(x);
}
}
}