题目
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
我的答案
/** * 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; };
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于