輸入一個鏈表的頭節(jié)點(diǎn)，從尾到頭反過來返回每個節(jié)點(diǎn)的值（用數(shù)組返回）故爵。示例：
輸入：head = [1,3,2]
輸出：[2,3,1]
鏈?zhǔn)酱鎯Y(jié)構(gòu)的便利在于增加瑟啃、刪除節(jié)點(diǎn)周叮，但如果我們要訪問某個節(jié)點(diǎn)的數(shù)據(jù)我們需要從頭結(jié)點(diǎn)開始一個一個的遍歷。
題目中要求我們要將鏈表的從尾到頭的打印宛渐，我們可以借助于棧的結(jié)構(gòu)FILO(First In Last Out)的特性來完成反向輸出竞漾，算法構(gòu)建一個O(n)大小的棧來存放從頭到尾遍歷后的結(jié)點(diǎn)，遍歷一次鏈表一次將數(shù)據(jù)存放到棧中窥翩，完成后將棧中數(shù)據(jù)依次出棧业岁，順序剛好就是鏈表從尾到頭的順序。
這里給出所需要用到的數(shù)據(jù)結(jié)構(gòu)：
// 單鏈表結(jié)點(diǎn)
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
// 使用數(shù)組實(shí)現(xiàn)的棧
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
}
}
棧的算法實(shí)現(xiàn)：
// 棧的實(shí)現(xiàn)
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
}
因遞歸的本質(zhì)就是一個棧的結(jié)構(gòu)寇蚊。上面用了棧結(jié)構(gòu)來實(shí)現(xiàn)算法笔时，那么自然可以聯(lián)想到遞歸的方式。如下代碼
// 遞歸實(shí)現(xiàn)
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
}
