剑指 Offer 06. 从尾到头打印链表-for循环和递归两种解法

题解

该题难度为简单。

解法一：两个for循环

• 1，先声明两个整型数组；
• 2，第一个for循环从头到尾记录链表的每个节点的值；
• 3，第二个for循环逆序记录链表的每个节点的值。

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    var re []int  //正序
    var er []int  //逆序
    for ;head != nil; {
        re = append(re,head.Val)  //从头到尾记录链表的每个节点的值
        head = head.Next
    }
    for i:=len(re)-1;i>=0;i-- {
        er = append(er,re[i])  //逆序记录链表的每个节点的值
    }
    return er  //返回
}

leetcode-cn执行：

执行用时：
0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：
3.5 MB, 在所有 Go 提交中击败了46.84%的用户

牛客网执行：

运行时间：3ms
超过2.29%用Go提交的代码
占用内存：868KB
超过39.69%用Go提交的代码

解法二：递归

两种解法：栈与递归

• 递归函数作用：将链表节点值逆序存入结果集
• 结束条件：当节点为空时
• 递归调用条件：当下一个节点不为空时

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return []int{}
    }
    res := reversePrint(head.Next)
    return append(res, head.Val)
}

leetcode-cn执行：

执行用时：
4 ms, 在所有 Go 提交中击败了63.34%的用户
内存消耗：
4.7 MB, 在所有 Go 提交中击败了28.61%的用户

牛客网执行：

运行时间：3ms
超过2.29%用Go提交的代码
占用内存：868KB
超过39.69%用Go提交的代码