剑指offer—面试题6：从尾到头打印单链表

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

输入：head = [1,3,2]
输出：[2,3,1]

链式存储结构的便利在于增加、删除节点，但如果我们要访问某个节点的数据我们需要从头结点开始一个一个的遍历。

题目中要求我们要将链表的从尾到头的打印，我们可以借助于栈的结构FILO(First In Last Out)的特性来完成反向输出，算法构建一个O(n)大小的栈来存放从头到尾遍历后的结点，遍历一次链表一次将数据存放到栈中，完成后将栈中数据依次出栈，顺序刚好就是链表从尾到头的顺序。

这里给出所需要用到的数据结构：

// 单链表结点

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

// 使用数组实现的栈
public struct Stack<T> {
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T){
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        return array.popLast()
    }
    
    public var top: T? {
        array.last
    }
}

栈的算法实现：

// 栈的实现
 func reversePrint(_ head: ListNode?) -> [Int] {
        if head == nil {
            return []
        }
        var head = head
        var stack = Stack<Int>()
        
        while head != nil {
            stack.push(head!.val)
            head = head?.next
        }
        
        var array = [Int]()
        while !stack.isEmpty {
            array.append(stack.pop()!)
        }
        return array
    }

因递归的本质就是一个栈的结构。上面用了栈结构来实现算法，那么自然可以联想到递归的方式。如下代码

// 递归实现
    var array = [Int]()

    func reversePrint(_ head: ListNode?) -> [Int] {
   
        guard let h = head else { return []}
        
        if h.next != nil {
            reversePrint(h.next)
        }
        array.append(h.val)
        
        return array
    }