【LeetCode】Linked List

能够完赛的人是鬼吧
本文会提到做 singular linked list 常犯错误、如何避免,与常见的技巧。
此系列 Leetcode 篇不介绍基本资料结构。

常见错误:null pointer

通常在写这类题目,就是个 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 断掉

没想清楚每一轮的步骤,导致 linked list 断掉,下一轮拿不到接下来该处理的 node。
可以画出来想。

常见错误:linked list 连出 cycle

这也是没想好而已,就.. 画出来想清楚
206. Reverse Linked List 这题可以注意一下。

使用 dummy node

时机

题目要回传一个新的 linked list (head node)时。

用法

先用 dummy = ListNode() 开个空的,
然後依据题目状况去连接 node,
最後 return dummy.next

优点

可以少掉判断到底哪个 node 是新的 head。
21. Merge Two Sorted Lists
206. Reverse Linked List

快慢指针

时机

  1. 判断 linked list 有没有 cycle(141. Linked List Cycle
  2. 回传 cycle 入口 node (142. Linked List Cycle II)。
  3. 还有取得 linked list 中点时。例如要做 merge sort (148. Sort List

核心想法

我觉得不太容易在第一次做就想到,所以稍微想过就可以去理解一下快慢指针做法。
以下是我的思考回路:

  1. 重复走到一个 node (n1)时,要怎麽透过另一个 node(n2) 知道我走过 n1?
  2. 不存额外资讯的话,那只有当指到 n1 与 n2 的 p1 p2 相遇时,才能有所判断处理吧?
    这里不提那三种作法了,直接去看题目吧。

必须能证明

快慢指针为何能 work?
背後的数学证明(简单就好)要能解释、多想几次,否则背答案是背不长久的。

LC 141 要能证明「fast pointer 会追到 slow pointer」:

  1. fast 在 slow 後一步,下一步的时候就会相遇
  2. fast 在 slow 後两步,下一步的时候就会差一步,回到 1.

LC 142 要能证明「fast pointer 会和 slow pointer 在 cycle 入口相遇」
...我看明天会不会记得补图

Recursive or Iterative?

蛮多 linked list 题目都可以用 recursive 的方式解出来。
但建议两个都要能快速写出来。
如果一开始想不到,或许 recursive 比较好下手,
但至少就要 O(n) 空间(递回深度的 stack frame),分析时要能想到。

总结

linked list 题目很建议要画一下,凭空想容易犯上述的错误。
我快不行了。


<<:  爱用iPhone的设计师可以多恐怖?

>>:  只要有 UGC,就是要花费大把青春跟 Spam 对抗

D 30 Python x Django 学习心得

从一开始接触Django到现在也一个月了 来简述跟总结一下自己认知到的技能 Django 网址传进来...

Day-21 SONY 的刁蛮三公主、PS3 步步艰辛的复兴之路

以 PS1 和 PS2 称霸於前两个世代的 SONY、在新的世代推出的主机当然就叫做 PS3。然而身...

DAY 17 制作 Nav Bar - Header

整个画面中最先看到的是 header 的 nav bar ,就让我们从这里开始刻吧! 首先在 App...

Day 2 - Using Google reCAPTCHA with ASP.NET Web Forms C#「我不是机器人」验证

=x= 🌵 CONTACT Page 寄信页的「我不是机器人」验证功能,後端实作。 Google r...

Day7 JS-Callback

在进入下一个NodeJS部份前想先讲一下Callback(回呼),这个概念不会占太大的篇幅,所以这篇...