剑指 Offer 06. 从尾到头打印链表

[Geekhyt]

原题链接

递归

1. “递” 阶段先走至链表末尾
2. head === null 为递归终止条件
3. “归” 阶段依次将每个节点上的值加入列表，即可实现链表值的倒序输出

const reversePrint = function(head) {
    return head === null ? [] : reversePrint(head.next).concat(head.val)
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

栈

1. 借助两个栈，先将链表中每个节点的值 push 进 stack1
2. 然后再从 stack1 中 pop 出每个节点的值放入 stack2

const reversePrint = function(head) {
    const stack1 = []
    const stack2 = []
    while(head) {
        stack1.push(head.val)
        head = head.next
    }
    const k = stack1.length;
    for (let i = 0; i < k; i++) {
        stack2[i] = stack1.pop()
    }
    return stack2
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)