第一题 环形链表
题目信息
解题思路
首先还是思考最暴力的解法
由示例 1 可知，有两个节点同时指向第二个节点，从而在单链表的根底上造成了闭环。即 pos0 和 pos3 领有着雷同的 next 指针
由示例 2 可知，对于指向头节点的状况，有必要退出哑节点辅助比拟 pos1 的 next 指针
所以咱们只有比对一遍所有节点的 next 指针，找到指向雷同的节点即可
然而很显著，该思路的复杂度为 O（n^2），个别状况下没有写进去的必要。
工夫复杂度高的起因次要是因为比照的过程过于麻烦，有太多重复性的操作。
对此再退出哈希表的概念优化一下，应用哈希表来存储所有曾经拜访过的节点
代码
func hasCycle(head *ListNode) bool {seen := map[*ListNode]struct{}{}
for head != nil {if _, ok := seen[head]; ok {return true}
seen[head] = struct{}{}
head = head.Next
}
return false
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。对于代码的 map 定义
复杂度剖析
工夫复杂度：O(N)，其中 N 是链表中的节点数。最坏状况下咱们须要遍历每个节点一次。
空间复杂度：O(N)，其中 N 是链表中的节点数。次要为哈希表的开销，最坏状况下咱们须要将每个节点插入到哈希表中一次。
另一种思路
快慢指针，永远滴神
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {return false}
slow, fast := head, head.Next
for fast != slow {
if fast == nil || fast.Next == nil {return false}
slow = slow.Next
fast = fast.Next.Next
}
return true
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。工夫复杂度：O(N)，其中 N 是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针达到链表尾部，链表中每个节点至少被拜访两次。
当链表中存在环时，每一轮挪动后，快慢指针的间隔将减小一。而初始间隔为环的长度，因而至少挪动 N 轮。
空间复杂度：O(1)。咱们只应用了两个指针的额定空间。
这很酷
第二题 二叉树的最大深度
题目信息
解题思路
遍历一遍树的所有节点并记录他的深度即可
常见的树的遍历办法即为广度优先搜寻和深度优先搜寻
本题求解为二叉树的深度 3，深搜显然更为简洁
代码
func maxDepth(root *TreeNode) int {
if root == nil {return 0}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1}
func max(a, b int) int {
if a > b {return a}
return b}
复杂度剖析
工夫复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度：O(height)，其中 height 示意二叉树的高度。递归函数须要栈空间，而栈空间取决于递归的深度，因而空间复杂度等价于二叉树的高度。