能够完赛的人是鬼吧
本文会提到做 singular linked list 常犯错误、如何避免,与常见的技巧。
此系列 Leetcode 篇不介绍基本资料结构。
通常在写这类题目,就是个 while 起手式吧,然後取得下一个 linked list node。
写完之後要检查所有取 node.next 或 node.val 的地方,在现在这个 while 条件下,node 有没有可能是 None,然後修改 while 条件。
当然可以一次想到位最好啦。
举个例子
1 while fast and fast.next:
2 fast = fast.next.next
3 slow = slow.next
line 1: 取 fast
的 next
-> 需判断此时 fast
不会为 None
-> while fast
才会进来这行,没问题
line 2: 取 fast.next
的 next
-> 需判断此时 fast.next
不会为 None
-> while fast.next
才会进来这行,没问题。
line 3: 取slow
的 next
-> 需判断此时 slow
不会为 None
-> 因为 slow 只会指到 fast 指过的,没问题。
没想清楚每一轮的步骤,导致 linked list 断掉,下一轮拿不到接下来该处理的 node。
可以画出来想。
这也是没想好而已,就.. 画出来想清楚
206. Reverse Linked List 这题可以注意一下。
题目要回传一个新的 linked list (head node)时。
先用 dummy = ListNode()
开个空的,
然後依据题目状况去连接 node,
最後 return dummy.next
。
可以少掉判断到底哪个 node 是新的 head。
21. Merge Two Sorted Lists
206. Reverse Linked List
我觉得不太容易在第一次做就想到,所以稍微想过就可以去理解一下快慢指针做法。
以下是我的思考回路:
快慢指针为何能 work?
背後的数学证明(简单就好)要能解释、多想几次,否则背答案是背不长久的。
LC 141 要能证明「fast pointer 会追到 slow pointer」:
LC 142 要能证明「fast pointer 会和 slow pointer 在 cycle 入口相遇」
...我看明天会不会记得补图
蛮多 linked list 题目都可以用 recursive 的方式解出来。
但建议两个都要能快速写出来。
如果一开始想不到,或许 recursive 比较好下手,
但至少就要 O(n) 空间(递回深度的 stack frame),分析时要能想到。
linked list 题目很建议要画一下,凭空想容易犯上述的错误。
我快不行了。
>>: 只要有 UGC,就是要花费大把青春跟 Spam 对抗
从一开始接触Django到现在也一个月了 来简述跟总结一下自己认知到的技能 Django 网址传进来...
以 PS1 和 PS2 称霸於前两个世代的 SONY、在新的世代推出的主机当然就叫做 PS3。然而身...
整个画面中最先看到的是 header 的 nav bar ,就让我们从这里开始刻吧! 首先在 App...
=x= 🌵 CONTACT Page 寄信页的「我不是机器人」验证功能,後端实作。 Google r...
在进入下一个NodeJS部份前想先讲一下Callback(回呼),这个概念不会占太大的篇幅,所以这篇...