【算法】剑指第二版面试题6 :从尾到头打印链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法】剑指第二版面试题6 :从尾到头打印链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1465字，纯文字阅读大概需要3分钟。

内容图文

题干

从尾到头打印链表

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\t", 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)

内容总结

以上是互联网集市为您收集整理的【算法】剑指第二版面试题6 :从尾到头打印链表全部内容，希望文章能够帮你解决【算法】剑指第二版面试题6 :从尾到头打印链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---