ARTS Week 9

Algorithm

This week’s LeetCode problem is 19. Remove Nth Node From End of List

Description: Given the head of a linked list, remove the nth node from the end of the list and return its head. Follow up: Could you do this in one pass?

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Solution Idea: There are two solutions. The first method is to iterate once to get the length of the chain table, and then the second time to determine the penultimate N node, and then remove it. The code is as follows.

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;
    }
}

The second method is to use a double pointer, specifying fast and slow pointers respectively, with a difference of N nodes between the fast and slow pointers, so that when the fast pointer traverses the end of the chain to null, the slow pointer is exactly the penultimate node. As the following example shows.

The code is as follows.

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

This week’s Review is for the following article: There is no ‘printf’

The author introduces an interesting phenomenon in the article. Before C99, the return value obtained by calling printf was not the return value of the printf function, but another value. The source file and the command to run are as follows.

$ cat ex.c
#include <stdio.h>
int main() {
	printf("Hello World!\n");
}
$ cc -ansi ex.c
$ . /a.out
Hello World!
$ echo $?
10

And the return value of printf should be 13, not 10.

$ cat ex.c
#include <stdio.h>
int main() {
	int a = printf("Hello World!\n");
	printf("%d\n", a);
}
$ cc -ansi ex.c
$ . /a.out
Hello World!
13
$ echo $?
3

By debugging and looking at the assembly code, the author found that gcc transforms printf into a puts function for output, which in turn causes the problem.

However, when I tried it on my own PC (openSUSE, GCC 11.2), I found that the problem does not occur :(

Tip

Java updates the value corresponding to a key in Map. In reality, there are practical applications, such as using Map to count the number of occurrences of each character, so when you encounter the same character, you need to update the number of occurrences. The easiest way to do this is to repeatedly put in the updated key-value pairs, because Map will automatically update value to the latest.

map.put(key, map.get(key) + 1);

Share

I don’t know, October is already 2/3 of the way through, feel too fast, many things have not had time to do before another month will pass, this month can only guarantee to complete the ARTS, and can not write other original articles, it seems to need more efforts ah! Go for it!