Dev - jw

逆序链表

题目 - ReversePrint

从尾到头打印链表（剑指offer 06）

难度：简单

分析

需要对单向链表进行逆序打印，通常可以考虑 2 个方法：

  • 方法 1：栈

    栈的特点是后进先出，即最后入栈的原生最先出栈。利用这个特性，我们使用栈将链表元素顺序倒置。

    从链表的头结点开始，依次将每个节点压入栈中，然后依次弹出栈内的元素，并存储到结果数组中

  • 方法 2：递归

    一个递归函数在执行过程中，会多次自我调用，而两个调用函数之间的链接与信息交换就是通过栈来进行的。

    利用递归：先执行到链表末端，回溯时依次将节点值加入结果数组，从而实现逆序输出

代码实现

栈思想

  1. 入栈：遍历链表，将每个节点值 push 入栈
  2. 出栈：将各个节点值 pop 出栈，存储到结果数组
func reversePrint(_ head: ListNode?) -> [Int] {
    var node = head
    // 定义栈
    var array = [Int]()
    var top = -1
    // 入栈
    while let next = node {
        array.append(next.val)
        top += 1
        node = next.next == nil ? nil : next.next
    }
    // 出栈
    var res = [Int]()
    while top > -1 {
        res.append(array[top])
        top -= 1
    }
    return res
}

难度：中等

  1. reversePrint函数的功能就是返回倒置链表的结果数组
  2. 递归结束条件是链表到尾节点
  3. 将链表值加入数组的等价关系式为array.append(node.val)
func reversePrint(_ head: ListNode?) -> [Int] {
    guard let node = head else {
        return [Int]()
    }
  	// 递归调用
    var array = reversePrint(node.next)
    // 加入结果数组
  	array.append(node.val)
    return array
}