Python技术迷

不尊重人的候选人,凭什么给你机会!

刚刷到这个帖子,真给我看乐了。

候选人一开始要40万,公司这边也没绕弯子,直接说预算就35万。你要是不接受,正常,谈薪嘛,本来就是你情我愿。问题是他当场拒了,过了4天又回来找HR,说35万也能接受。

这就有点尴尬了。

Image

HR那边也很干脆:不考虑了,已经重新招人了。很多人可能觉得公司小气,少个人选还摆谱。但换个角度看,招聘不是菜市场砍价,你转头走了,又发现外面没人接,再回来让人给你留坑,凭啥呢?

而且这事最伤的不是钱,是态度。你可以谈,你可以拒,你也可以觉得自己值40万,没问题。但你前面表现得像“你们配不上我”,后面又回来“其实也行”,HR心里能不犯嘀咕吗?

今日算法题

翻转链表,别上来就背递归

链表题最烦的地方,不是代码长,是指针一旦断错,后面全是空。

翻转链表这题,我一般不先想递归。递归当然能写,但排查起来不如迭代踏实。尤其面试现场,手一抖把 next 覆盖掉,链表后半截直接丢了。

题目大概是这样:

给一个单链表:

1 -> 2 -> 3 -> 4 -> 5 -> None

翻转成:

5 -> 4 -> 3 -> 2 -> 1 -> None

这题真正要盯住的不是“翻转”两个字,而是每次处理当前节点时,必须先把后路留住。

我会先写这三个指针:

prev:已经翻好的链表头
cur :当前正在处理的节点
nxt :先临时存一下 cur.next,防止链表断了找不回来

代码就这么几行,别加戏。

classNode:
def__init__(self, val: int):
        self.val = val
        self.next = None


defreverse_list(head: Node | None) -> Node | None:
    prev = None
    cur = head

while cur isnotNone:
        nxt = cur.next      # 先把后面的节点记下来
        cur.next = prev     # 当前节点反手指向前面
        prev = cur          # prev 往前挪
        cur = nxt           # cur 继续处理原链表后面

return prev

这里最容易写错的是顺序。

有些人会直接这么写:

cur.next = prev
cur = cur.next

这地方我第一眼就不太信。因为 cur.next 已经被你改成 prev 了,再拿它往后走,走的就不是原链表了。原来的下一个节点已经丢了。

所以 nxt = cur.next 必须放在改指针之前。

拿 1 -> 2 -> 3 走一遍:

第一次:

prev = None
cur  = 1
nxt  = 2

执行完后:

1 -> None
prev = 1
cur  = 2

第二次:

2 -> 1 -> None
prev = 2
cur  = 3

第三次:

3 -> 2 -> 1 -> None
prev = 3
cur  = None

循环停掉,prev 就是新头节点。

如果要自己测一下,不用整太复杂,写个小工具把链表打出来就行:

defbuild_list(values: list[int]) -> Node | None:
    dummy = Node(-1)
    tail = dummy

for num in values:
        tail.next = Node(num)
        tail = tail.next

return dummy.next


defdump(head: Node | None) -> list[int]:
    ans = []
    cur = head

while cur isnotNone:
        ans.append(cur.val)
        cur = cur.next

return ans


head = build_list([1, 2, 3, 4, 5])
new_head = reverse_list(head)

print(dump(new_head))  # [5, 4, 3, 2, 1]

这题的时间复杂度是 O(n),每个节点只碰一次。

空间复杂度是 O(1),没有新建链表,只是改了指针方向。

递归版本也能写,但我不太建议一开始就背递归。链表翻转这种题,迭代写法更像现场排问题:先保留现场,再改指针,最后往前推进。顺序对了,代码自然就短。