Algorithm
本周的 LeetCode 题目为：19. 删除链表的倒数第 N 个结点
题目简介：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。**进阶：**你能尝试使用一趟扫描实现吗？示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
题目思路：一共有两种解法。第一种方法就是先遍历一次得到链表的长度，而后第二次遍历时就可以确定倒数第 N 个结点，进而进行移除。代码如下：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode curr = head;
while (curr != null) {
length++;
curr = curr.next;
}
int goal = length - n;
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
for (int i = 0; i < goal; i++) {
prev = prev.next;
}
prev.next = prev.next.next;
return dummy.next;
}
}
第二种方法是使用双指针，分别指定快(fast)、慢(slow)指针，快慢指针之间相差 N 个结点，当快指针遍历到链表尾为 null 时，慢指针正好是倒数第 N 个结点。如下例所示：
1->2->3->4->5->null, N = 2
f f f f
s s s s
最终代码为：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = head;
ListNode slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
Review
本周 Review 的英文文章为：并没有 printf
作者在文章介绍了一个有趣的现象，在 C99 之前，调用 printf 得到的返回值并不是 printf 函数的返回值，而是另一个值。源文件和运行的命令如下：
$ cat ex.c
int main() {
printf("Hello World!\n");
}
$ cc -ansi ex.c
$ ./a.out
Hello World!
$ echo $?
10
$
而 printf 的返回值应该是 13，而不是10。
$ cat ex.c
int main() {
int a = printf("Hello World!\n");
printf("%d\n", a);
}
$ cc -ansi ex.c
$ ./a.out
Hello World!
13
$ echo $?
3
$
作者通过调试，查看汇编代码，发现 gcc 会把 printf 转变为 puts 函数进行输出，进而导致了这个问题。
但是，当我在自己的电脑上尝试（openSUSE、GCC 11.2），却发现并不会出现在这个问题 😦
Tip
Java 中更新 Map 中某个键对应的值。现实中也有实际应用，如利用 Map 来统计每个字符的出现次数，因此遇到相同的字符后，就需要更新出现次数。最简单的办法就是重复放入更新后的键值对，因为 Map 会自动更新 value 为最新的。
map.put(key, map.get(key) + 1);
Share
不知不觉中，10月已经过了2/3了，感觉太快了，好多事还没来得及做就又要过去一个月了，这个月只能保证完成 ARTS，而无法写出其他原创文章，看来还需要多多努力啊！加油！
|