25 分钟

求职冲刺

数据结构基础

链表、栈、队列、哈希表

实现链表和常见操作
栈和队列的应用
哈希表原理

链表

示例代码（可运行）

Python 0%

1class ListNode:

2 def __init__(self, val=0, next=None):

3 self.val = val

4 self.next = next

6# 创建链表 1→2→3

7head = ListNode(1, ListNode(2, ListNode(3)))

9# 遍历

10def print_list(head):

11 vals = []

12 while head:

13 vals.append(str(head.val))

14 head = head.next

15 print(" → ".join(vals))

17print_list(head)

19# 反转链表

20def reverse(head):

21 prev = None

22 while head:

23 next_node = head.next

24 head.next = prev

25 prev = head

26 head = next_node

27 return prev

29print_list(reverse(ListNode(1, ListNode(2, ListNode(3)))))

栈和队列

示例代码（可运行）

Python 0%

1# 栈：LIFO 后进先出

2stack = []

3stack.append(1) # 入栈

4stack.append(2)

5print(stack.pop()) # 2 出栈

7# 括号匹配（栈经典应用）

8def is_valid(s):

9 pairs = {")":"(", "]":"[", "}":"{"}

10 stack = []

11 for c in s:

12 if c in "([{":

13 stack.append(c)

14 elif stack and stack[-1] == pairs[c]:

15 stack.pop()

16 else:

17 return False

18 return not stack

20print(is_valid("({[]})")) # True

21print(is_valid("([)]")) # False

23# 队列：FIFO 先进先出

24from collections import deque

25queue = deque()

26queue.append(1) # 入队

27queue.append(2)

28print(queue.popleft()) # 1 出队

哈希表原理

示例代码（可运行）

Python 0%

1# Python字典就是哈希表

2# 模拟哈希冲突处理（链地址法）

3class SimpleDict:

4 def __init__(self, size=10):

5 self.size = size

6 self.buckets = [[] for _ in range(size)]

8 def _hash(self, key):

9 return hash(key) % self.size

11 def __setitem__(self, key, value):

12 idx = self._hash(key)

13 for i, (k, v) in enumerate(self.buckets[idx]):

14 if k == key:

15 self.buckets[idx][i] = (key, value)

16 return

17 self.buckets[idx].append((key, value))

19 def __getitem__(self, key):

20 idx = self._hash(key)

21 for k, v in self.buckets[idx]:

22 if k == key:

23 return v

24 raise KeyError(key)

26d = SimpleDict()

27d["name"] = "小明"

28d["age"] = 20

29print(d["name"], d["age"])

预测输出

stack=[1,2,3]
print(stack.pop())

找 Bug反转链表时没保存next节点就改了head.next，链表就断了。

def reverse(head): prev=None while head: head.next=prev prev=head

填空题填写空白处的代码

from collections import deque q = deque() q.append(1) q.popleft() #

选择题

括号匹配用什么数据结构？

资深工程师加餐

底层原理 · 大厂视角 · 工程经验，点卡片展开

时间复杂度看「基本操作次数随输入规模 n 的增长量级」，空间复杂度看额外占用的内存；还要区分最好、最坏、平均与均摊。面试时先给能工作的暴力解并说明其复杂度，再一步步优化到更优——面试官评估的往往是你的推导过程，而不只是你是否背出了最优答案。

挑战任务

数据结构挑战

简单+50 XP

用栈实现浏览器前进后退。

数据结构挑战

Python 0%

2 个测试用例

课后作业

循环队列

中等+20 XP

用数组实现固定大小循环队列。

循环队列

Python 0%

1 个测试用例