【剑指Offer 3.从尾到头打印链表】

题目描述
思路分析
AC 代码
总结

掘金团队号上线，助你 Offer 临门！点击查看详情

一、题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

示例1

输入

{67,0,24,58}

返回值

[58,24,0,67]

二、思路分析

难度：较难

读完题目需要注意一点，尽管题目要求是从尾到头打印链表，但并不是让我们返回一个链表再打印，而是返回一个数组，一定要避免审题不清导致的编码错误。解决这个问题，一般有两种思路，第一种就是使用递归法，嵌套调用拼接当前节点，最终得到从尾到头的连接数组。具体实现请看方法一。

第二种方法就是一般思路，利用一个中间数组，然后逆序拼接得到最终的目标数组。这种方法最容易被想到，也最容易理解。具体实现请看方法二。

三、AC 代码

语言：Go

方法一

代码：

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param head ListNode类 
 * @return int整型一维数组
*/
func printListFromTailToHead( head *ListNode ) []int {
    if head == nil {
        return []int{}
    }
    return append(printListFromTailToHead(head.Next), head.Val)
}
复制代码

方法二

代码：

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param head ListNode类 
 * @return int整型一维数组
*/
func printListFromTailToHead( head *ListNode ) []int {
    tmp := make([]int, 0)
    res := make([]int, 0)
    for head != nil {
        tmp = append(tmp, head.Val)
        head = head.Next
    } 
    length := len(tmp)
    for length > 0 {
        res = append(res, tmp[length-1])
        length--
    }
    return res
}
复制代码