JS 剑指Offer(四) 从尾到头打印链表

题目:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

首先定义一下链表中的节点,关于链表这个数据结构在另外一篇文章中会详细讲

         function ListNode(val) {
this.val = val;
this.next = null;
}

理清一下思路,我们要反转一个链表,可以遍历链表,将链表中的元素存到一个数组中,然后按照反转的顺序保存

好了,思路清晰了,那我们当然是要用栈这个数据结构,要记住,在改变顺序或者操作数组的时候,是和栈分不开的

         var reserveprint = function(head){
const stack = []
let node = head
while(node){
stack.push(node.val);
node = node.next;
} const reverse = []
while(stack.length){
reverse.push(stack.pop())
} return reverse
}

这里用到了辅助栈的想法,首先建立一个辅助栈stack,遍历一遍整个单链表,将单链表中节点的value顺序push到stack里

此时,辅助栈stack中元素的顺序是和单链表相同的,接下来要做的自然就是反转一下这个数组,很简单,将辅助栈stack中尾部的元素取出来依次push到最终的结果栈reverse中即可

以上应用辅助栈的想法很好,但是我个人在使用JS的时候很少会这么麻烦,因为JS数组方法中有unshift,可以直接向数组的开头不断添加元素,更精简的方法如下

         function reversePrint2(){
let res = []
let head = this.head
while(head){
res.unshift((head.val))
head = head.next
}
return res
}

好了,以上就是JS剑指Offer的第四题,从尾到头打印链表,如果小伙伴们有更好的方法,不妨在评论区留言哦

上一篇:LeetCode练题——70. Climbing Stairs


下一篇:解决Undefined symbols for architecture x86_64: 报错 和 ld: warning: ld: warning: ignoring file警告