面试题6: 从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
第一种 链表反转
//我们把链反转
public ArrayList<Integer> reverseList(ListNode head) {
ArrayList<Integer> revList = new ArrayList<>();
if (head == null )
return revList;
if (head.next == null) {
revList.add(head.val);
return revList;
}
ListNode prev = head;
ListNode curr = head.next;
ListNode next ;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head.next = null;
head = prev;
ListNode temp = head;
while (temp != null) {
revList.add(temp.val);
temp = temp.next;
}
return revList;
}
输入一个链表，从尾到头反过来打印每个节点的值
第二种 用栈
//输入一个链表，从尾到头反过来打印每个节点的值
//思路一： 只是打印，我们可以把链放到栈里，然后从栈顶一个个打印
public void printTailToHead_stack(ListNode head) {
LinkedList<Integer> stack = new LinkedList<>();
ListNode n = head;
while (n != null) {
stack.push(n.val);
n = n.next;
}
Integer i;
while ((i = stack.poll()) != null) {
System.out.print(i + " ");
}
System.out.println();
}
第三种 用递归
//思路二： 可以通过递归，遍历下一个然后再打印
//不过递归，如果链比较长的话，可能会导致调用栈溢出
public void printTailToHead_recusion(ListNode head) {
if (head != null) {
if (head.next != null)
printTailToHead_recusion(head.next);
System.out.print(head.val + " ");
}
}