手撕代码热门题

① 牛客 · BM6 判断链表中是否有环【简单】

  • 方法1：双指针（快、慢指针）【时间复杂度：O(n)、空间复杂度：O(1)】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return head
        # 快慢指针
        slow = head
        fast = head

        while slow and fast:
            slow = slow.next
            if fast.next:
                fast = fast.next.next
            else:
                return False
            if slow == fast:
                return True
        
        return False
  • 方法2：哈希表（存节点，判断是否有环）【时间复杂度：O(n)、空间复杂度：O(n)】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return head
        visited = set()
        while head:
            if head in visited:
                return True
            visited.add(head)
        return False

② 牛客 · BM1 反转链表【简单】

  • 方法1：栈实现
  • 方法2：双链表

③ 合并两个有序链表【简单】

  • 方法1：双指针

④ 二叉树遍历

  • 方法1：递归（深度优先）
  • 方法2：列表（广度优先）

⑤ 单利模式

  • 方法1：

⑥ LRU缓存

  • 方法1：（最优实现）双向链表 + 哈希

⑦ 合并有序数组

  • 方法1：双指针

⑧ 快排

⑨ 两数之和

  • 方法1：哈希
    1
    2
    3
    4
    5
    6
    hashset = dict()
    for i in range(len(nums)):
        if target - nums[i] in hashset:
            return [hashset[target-nums[i]], i]
        hashset[nums[i]] = i
    return []

⑩ 最长回文字串

  • 方法1：贪心算法

⑪ 二叉树最近公共祖先

核心思路：遍历

（其他）判断回文字符串

（其他）两段字符创的最大公共字符串

（其他）有序链表转换二叉搜索树

（其他）两个栈实现队列

（其他）三个小城交替打印ABC

（其他）判断回文字符串