LeetCode 165 https://leetcode.cn/problems/compare-version-numbers/description/ 难度：中等 使用两个指针，遍历两个字符串，直到找到’.’，将每一段的版本号转换为整数，比较两个整数是否相等。整数初始化为 0，以处理这一段版本号缺失的情况。 时间复杂度：O(n+m)，其中 m 是字符串 version1 的长度，n 是字符串 version2 的长度。 空间复杂度：O(1)，我们只需要常数的空间保存若干变量。 ...
LeetCode 142 https://leetcode.cn/problems/linked-list-cycle-ii/description/ 难度：中等 环形链表 II，比环形链表 I 多了需要找到入环节点。 设头节点到入环口需要走 a 步，环长为 c。快慢指针相遇时，慢指针走了 b 步，快指针走了 2b 步。设快指针比慢指针多走了 k 圈，即 2b - b = kc，得 b = kc。 慢指针在入环口开始，在环中走了 b - a = kc - a 步到达相遇点。这说明从相遇点开始，再走 a 步，就恰好到达相遇点。 如果让头节点和慢指针同时走，恰好 a 步后二者必定相遇，且相遇点就在入环口。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...
LeetCode 160 https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 难度：简单 最简单的方法是使用哈希集合来记录访问过的节点。除此之外还有双指针的做法。 我来到你的城市，走过你来时的路。 初始化两个指针 p = headA, q = headB。 不断循环，直到 p == q。 每次循环，p 和 q 各向后走一步。具体来说，如果 p 不是空节点，那么更新 p 为 p->next，否则更新 p 为 headB；如果 q 不是空节点，那么更新 q 为 q->next，否则更新 q 为 headA。 循环结束时，如果两条链表相交，那么此时 p 和 q 都在相交的起始节点处，返回 p；如果两条链表不相交，那么 p 和 q 都走到空节点，所以也可以返回 p，即空节点。 时间复杂度：O(m+n)，其中 m 是第一条链表的长度，n 是第二条链表的长度。除了交点，每个节点会被指针 p 访问至多一次，每个节点会被指针 q 访问至多一次。 空间复杂度：O(1)。 ...
LeetCode 141 https://leetcode.cn/problems/linked-list-cycle/description/ 难度：简单 这道题目的做法是快慢指针。快指针每次走两步，慢指针每次走一步，如果快慢指针相等，说明链表有环。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...
LeetCode 88 https://leetcode.cn/problems/merge-sorted-array/description/ 难度：简单 本题最简单的思路是使用额外的空间存储，最后复制回 nums1。那么有没有什么方案可以避免额外空间？答案是使用逆向双指针算法。从最后一个元素开始，将结果赋值到 nums1。这样可以避免 nums1 中元素被覆盖的问题。 时间复杂度：O(m+n)。 空间复杂度：O(1)。仅用到若干额外变量。 ...
LeetCode 15 https://leetcode.cn/problems/3sum/description/ 难度：中等 首先，由于输出的顺序不重要，可以先将数组进行排序。然后，枚举第一个数，转化为两数之和 II（LeetCode 142）。为了排除重复答案，如果 i，j，k 与上一个元素相同，需要去重。 时间复杂度：O(\(n^ 2\))，其中 n 为 nums 的长度。排序 O(nlogn)。外层循环枚举第一个数，就变成 167. 两数之和 II - 输入有序数组 了，做法是 O(n) 双指针。所以总的时间复杂度为 O(\(n^ 2\))。 空间复杂度：O(1)。返回值不计入。忽略排序的栈开销。 ...