面试题 6. 从尾到头打印链表
题目描述
输入一个链表的头结点,从尾到头反过来打印出每个结点的值。
Java 实现
ListNode Class
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
return val + "->" + next;
}
}
使用递归
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
if (listNode == null) {
return res;
}
res.addAll(printListFromTailToHead(listNode.next));
res.add(listNode.val);
return res;
}
}
使用头插法
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
ListNode head = new ListNode(-1);
while (listNode != null) {
ListNode newHead = listNode.next;
listNode.next = head.next;
head.next = listNode;
listNode = newHead;
}
while (head.next != null) {
res.add(head.next.val);
head = head.next;
}
return res;
}
}
使用栈
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.isEmpty()) {
res.add(stack.pop());
}
return res;
}
}