一、题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

二、我的题解 – 正向遍历，反向return

1. 我的方法就是正向遍历链表，按序存储其值，再反向后返回。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {

	s := []int{}  //按顺序存储链表的值
	rs := []int{} //反序存储链表的值
	
	//这个判断很重要！！！如果 head 为空，则会引发panic: nil pointer
	if head != nil {   //链表的长度至少为 1。 
		for {
			s = append(s, head.Val)
			if head.Next != nil {
				head = head.Next
			} else {    //没有下一个节点时，结束循环
				break
			}
		}
		for i := len(s) - 1; i >= 0; i-- {   //反序s
			rs = append(rs, s[i])
		}
	} else {
		return rs
	}

	return rs
}

评判结果：

可见时间消耗还是很低的。

但是空间复杂度还是需要改进，用 “反转链表” （见下文三）可以降低内存消耗。因为可以少用一个数组。

2. 完整代码

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

//扩充链表
func extendlink(link *ListNode, v []int) *ListNode {

	var newnode *ListNode
	temp := link

	if link != nil {
		for {
			if temp.Next == nil {
				for i := 0; i < len(v); i++ {
					newnode = new(ListNode)
					newnode.Val = v[i]
					temp.Next = newnode
					temp = temp.Next
				}
				break
			} else {
				temp = temp.Next
				continue
			}
		}
		return link
	} else {
		return link
	}

}


//从尾到头反向返回每个节点的值
func reversePrint(head *ListNode) []int {

	s := []int{}
	rs := []int{}
	if head != nil { //链表的长度至少为 1
		for {
			s = append(s, head.Val)
			if head.Next != nil {
				head = head.Next
			} else {
				break
			}
		}
		for i := len(s) - 1; i >= 0; i-- {
			rs = append(rs, s[i])
		}
	} else {
		return rs
	}

	return rs
}

func main() {
	node := new(ListNode) //头结点
	node.Val = 1

	node1 := extendlink(node, []int{2, 3, 4}) //加长链表

	fmt.Println(reversePrint(node1))

}

注意：

当函数传入的是一个指针类型的时候，一定要进行空值的判断！！！

空指针会引发 panic ！！！

三、改进 – 先反转链表，再按序输出

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {

	if head == nil {
		return nil
	}

	s := []int{}

	var prev *ListNode   //反转链表的过程中用到了三个辅助指针：prev 、curr 、next 
	var curr *ListNode
	var next *ListNode

	curr = head
	prev = nil //初始化 prev 为nil，为了反转头结点时，使其指向 nil

	//反转链表
	for curr != nil {
		next = curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	head = prev

	//遍历反转后的链表
	for {
		s = append(s, head.Val)
		if head.Next == nil {
			break
		}
        head = head.Next
	}

	return s
}