【剑指 offer】从尾到头打印链表

本贴最后更新于 1300 天前,其中的信息可能已经时异事殊

题目

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

我的答案

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {number[]} */ var reversePrint = function(head) { const valueStack = []; let currentNode=head; while(currentNode){ valueStack.push(currentNode.val); currentNode=currentNode.next; } return valueStack.reverse() };

优化

上述做法非常节省内存,但是用时较长,这是因为数组的 reserve 话费时间较长,所以想要提升速度,就需要不出现需要数组反转的情况。当改变思路,在数据加入数组时,使用 unshift,这样速度也能有所提升。但是并不是我们想要的最快的结果。

最快的方法是,使用两个指针先将列表反转,然后沿着反转后的列表记录数组。

翻转列表:记录第一个和第二个节点,将第二个节点的 next 指向第一个,以此类推。

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {number[]} */ var reversePrint = function(head) { const valueStack = []; let currentNode=head; let preNode=null; while(currentNode){ const nextCurrent=currentNode.next; currentNode.next=preNode; preNode=currentNode; currentNode=nextCurrent; } while(preNode){ valueStack.push(preNode.val); preNode=preNode.next; } return valueStack; };

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...