反向输出链表 - LinkWorld Algorithm Blog

一、题目

输入个链表的头结点，从尾到头反过来打印出每个结点的值。

二、解题思路

Notzuonotdied的思路

使用递归实现，代码非常的简洁。

/**
 * 递归从后往前输出链表
 *
 * @param root 根结点
 * */
fun printListInverselyUsingRecursion(root: ListNode) {
    fun recursion(root: ListNode) {
        if (root.next == null) {
            println("为空——\\(≧▽≦)/~啦啦啦")
        } else {
            recursion(root.next!!)
        }
        print("${root.value} ")
    }
    recursion(root)
}

递归的代码，干净整洁。但是，一旦链表的长度过于长的时候，就会导致递归的层次很深，从而有可能导致函数调用栈溢出。

因此，将代码由递归改为栈的方式进行。

思路：首先从头到尾遍历一遍链表元素并逐步压入栈中。之后，将栈中元素依次弹出（pop）。

代码实现

import java.util.Stack

/**
 * 结点
 *
 * @param value 结点的值
 * @param next 下一个结点
 * */
class ListNode(var value: Int, var next: ListNode?)

/**
 * 使用栈从后往前输出链表
 *
 * @param root 根结点
 * */
fun printListInverselyUsingIteration(root: ListNode) {
    var rootBackup = root

    val stack = Stack<ListNode>()
    while (true) {
        if (rootBackup.next == null) {
            stack.push(rootBackup)
            break
        } else {
            stack.push(rootBackup)
            rootBackup = rootBackup.next!!
        }
    }
    println("\n栈开始输出啦～")
    var tmp: ListNode
    while (!stack.isEmpty()) {
        tmp = stack.pop()
        print("${tmp.value} ")
    }
}

/**
 * 递归从后往前输出链表
 *
 * @param root 根结点
 * */
fun printListInverselyUsingRecursion(root: ListNode) {
    fun recursion(root: ListNode) {
        if (root.next == null) {
            println("为空——\\(≧▽≦)/~啦啦啦")
        } else {
            recursion(root.next!!)
        }
        print("${root.value} ")
    }
    recursion(root)
}

fun main(args: Array<String>) {
    var root = ListNode(0, null)
    val backupRoot: ListNode = root

    // 初始化一个链表
    for (i in 1..10) {
        root.next = ListNode(i, null)
        root = root.next!!
    }
    // 输出不为空的链表
    printListInverselyUsingRecursion(backupRoot)
    printListInverselyUsingIteration(backupRoot)
    // 输出空链表
    // Kotlin自动类型检查，不支持传递空，这里就不测试了
}

输出结果

为空——\(≧▽≦)/~啦啦啦
10 9 8 7 6 5 4 3 2 1 0 
栈开始输出啦～
10 9 8 7 6 5 4 3 2 1 0