题目描述:输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。比如下面的链表:![](https://img-blog.csdnimg.cn/direct/9b226370740240c28406f276f345283a.png)
返回的数组为
[3,2,1]
思路及解答:
- 使用栈
- 使用递归调用
- 使用头插法
借助栈实现:先把元素里面的元素从头到尾遍历取出放在栈里面,然后再把栈的元素去出来放在ArrayList
里面。主要利用了栈的先进后出的规则,这样就可以实现倒序的功能。
首先是栈的初始化定义:
public class ListNode{
int val;
ListNode next = null;
ListNode(int val){
this.val = val;
}
}
Java
代码实现如下:
import java.util.ArrayList;
import java.util.Stack;
public class Solution{
public ArrayList<Integer>printListTailToHead(ListNode listNode){
Stack<Integer> stack = new Stack<>();
while(listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> results = new ArrayList<>();
while(!stack.isEmpty()){
results.add(stack.pop());
}
return results;
}
}
使用递归调用: 递归方法的调用过程,就是一个天然的栈调用的过程,只需要判断当前节点是不是为空,为空则不输出,不为空则递归下一个节点,对下一个节点处理之后,把结果使用ArrayList.addAll()
加到结果中,再把自身加到结果中。
import java.util.ArrayList;
import java.util.Stack;
public class Solution{
public ArrayList<Integer> printListFormTailToHead(ListNode listNode){
ArrayList<Integer> = results = new ArrayList<>();
if(listNode != null){
//对后面的元素进行处理
results.addAll(printListFormTailTohead(listNode.next));
//最后添加自身
results.add(listNode.val);
}
return results;
}
}
头插法: 我们遍历每一个节点,然后把它插入到头部,这样一直遍历到尾的时候,就相当于将整个链表都反转一遍了,然后再从头到尾遍历放到ArryList
即可。
Java实现代码如下:
import java.util.ArrayList;
import java.util.Stack;
public class Solution{
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
ListNode head = new ListNode(-1);
while(listNode != null){
//先把当前node的next保存起来
ListNode temp = listNode.next;
//把当前节点的next指针指向head的下一个节点
listNode.next = head.next;
//把head的next指向当前节点
head.next = listNode;
//将遍历的指针指向了遍历的下一个元素
listNode = temp;
}
ArrayList<Integer> results = new ArrayList<>();
head = head.next;
//遍历输出
while(head != null){
results.add(head.val);
head = head.next;
}
return results;
}
}
总结:通过以上三种方法的操作,均能实现题目中所要求的输出结果,同时在实际操作中,复习到了数据结构中的栈的相关操作、递归调用以及链表的使用等。因此在进行解题前,需要巩固一下相关知识点,这样更加有利于理解对于本题的解答。