关于golang:golangleetcode初级环形链表

第一题 环形链表

题目信息

解题思路

首先还是思考最暴力的解法
由示例 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 示意二叉树的高度。递归函数须要栈空间，而栈空间取决于递归的深度，因而空间复杂度等价于二叉树的高度。