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

题目

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

我的答案

/**
 * 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;
};
​