题干
从尾到头打印链表
func printListFromTailToHead(head *Node) {}
直接思路
先访问后打印，先入后出: 借助栈实现
需要分享的思路
借助系统本身的调用栈。
代码编写思路
构造一个系统调用栈的运行情况: 不断入栈递归函数(2个指令 1.访问剩余链表 2.打印当前节点)
处理节点1开头的节点(出栈被执行)
打印节点1
==> 入栈一个入参为节点2的递归函数(2个指令)
处理节点2开头的节点(出栈被执行)
打印节点2
打印节点1
==> 入栈一个入参为节点3的递归函数(2个指令)
处理节点3开头的节点(出栈被执行)
打印节点3
打印节点2
打印节点1
==>
....
==> 到达递归边界:入参节点=nil
打印节点n(出栈被执行)
...
打印节点3
打印节点2
打印节点1
package main
import (
"fmt"
)
type Node struct{
Val int
Next *Node
}
func printListFromTailToHead(head *Node) {
if head != nil {
printListFromTailToHead(head.Next)
fmt.Printf("%d ", head.Val)
}
}
func createLinkedList(arr []int) *Node{
if len(arr) == 0{
return nil
}
head := &Node{Val:arr[0]} // YC: 除了头结点,其他节点都是在设置next指针时创建的
cur := head // 需要设置一个cur节点,表示当前正在被设置的节点(val已知,next还未知)
for i:=1; i<len(arr); i++ {
cur.Next = &Node{Val:arr[i]}
cur = cur.Next
}
return head
}
func printLinkedList(head *Node){
for head != nil{
fmt.Print(head.Val," -> ")
head = head.Next
}
fmt.Println("nil")
}
func main() {
head := createLinkedList([]int{1,2,3})
printLinkedList(head)
printListFromTailToHead(head)
}
//outpu
1 -> 2 -> 3 -> nil
3 2 1
2种思路的选择
递归可能导致调用栈溢出。
复杂度
时间复杂度: O(n)
空间复杂度: O(n),因为每次递归，调用栈都要用掉一点,用掉n*x的调用栈内存，所以O(n)