Unity链表和树的面试题

以下是两道常见的Unity链表和树的面试题：

1. 链表相关面试题

（1）反转链表

问题描述：给定一个单向链表的头节点，将这个链表反转过来。

思路：遍历链表，将每个节点的 next 指针指向前一个节点即可。

（2）判断链表是否有环

问题描述：给定一个单向链表的头节点，判断这个链表是否有环。

思路：使用快慢指针法，让两个指针同时从头节点出发，快指针每次移动两个节点，慢指针每次移动一个节点。如果快指针能够追上慢指针，那么说明链表有环。

2. 树相关面试题

（1）二叉树的遍历

问题描述：给定一棵二叉树，输出它的前序遍历、中序遍历和后序遍历结果。

思路：使用递归算法或者栈来实现遍历。前序遍历先输出根节点，然后递归输出左子树和右子树；中序遍历先递归输出左子树，然后输出根节点，最后递归输出右子树；后序遍历先递归输出左子树和右子树，最后输出根节点。

（2）求二叉树的深度

问题描述：给定一棵二叉树，求它的深度（即最大深度）。

思路：使用递归算法，分别求左子树和右子树的深度，然后取两者的较大值，再加上根节点的深度1即为整棵树的深度。