This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Today continues to take a day off from home and come to nuggets early to write an article. In fact, with modern work collaboration software and collaborative methods, it is very unlikely that a weekday vacation will be completely away from work. Although it is nominally a vacation at home, it is actually a semi-on-duty state. After the start of autumn, the first cup of milk tea in autumn began in the circle of friends. I do not know when it started, but it seems that there is no such thing as the first cup of milk tea in summer or the first cup of milk tea in winter. Recently, I often watch other people’s business videos in Toutiao. There are second-hand car dealers, people who do fast food, people who sell roast duck, all kinds. I suddenly realized that running a shop or a business of my own has a lot of interesting links. Although the business is small, it is a complete business, from raw material purchase, production, sales and after-sales service. The cruel thing is, if any link goes wrong, your business as a whole will fail, or at least not make money. But if you really run a business completely, it is also very fulfilling. This kind of small business is completely different from the job of a programmer. The programmer is a very narrow part of a larger business. There are really too many more important factors to make the business work. However, as mentioned above, the failure of any link will lead to the overall failure of the business. Doing your job well will also help the success of the whole big business. Writing so much, I hope that one day I can have the opportunity to really run a small business of my own. From nothing, from weak to strong, I should also have a great sense of achievement.

Again, the programmer should continue to improve their skills, today continue to do Leetcode problem 19.

The title

Give you a linked list, remove the NTH node from the reciprocal of the list, and return the head node of the list. Advanced: Can you try using a scan implementation?

Example 1:

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

Example 2: Input: head = [1], n = 1 Output: []

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

Train of thought

This problem I understand is mainly familiar with the list of data structure, algorithmic thought reflected not much. To delete the reciprocal NTH node, the next of the reciprocal n+1 node should be pointed to the reciprocal NTH node, that is, the next of the reciprocal NTH node. What beats you, most likely, is the case of the boundary. Consider two boundaries here:

  • n = 1

The last node is removed, and the next of the penultimate node points to the next of the last node. The next of the last node is empty, but that doesn’t cause problems.

  • n = len

In this case, we’re deleting the first node, notice that the method lets us return the head node, in this case, we’re returning the second node, so we have to do something special in this case so can we have a method in 1 that doesn’t have to do something special in case 2? In this case, since the total length of the list is len+1, case 2 cannot exist. After deleting the node, we need to return the head node of the new list, as long as we return the next of dummy.

The logic of the question is not difficult:

  1. Dummy (next) : dummy (next);
  2. Press all nodes in the list in order;
  3. Pop n nodes from the stack;
  4. Another node pops up, next points to next of next;
  5. Return to the dummy. Next;

, of course, there is a risk, it is after all the node pressure stack, may be out of memory, want to save in the province, only a traversal of the length, and then calculate the node is positive we are trying to remove the first m nodes, then traverse 1 time to delete it, so save the memory, but more traversal 1 time, so it’s just an exchange of space and time trade-off.

Java version code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Stack<ListNode> stack = new Stack<>();
        ListNode now = dummy;
        while (now != null) {
            stack.push(now);
            now = now.next;
        }
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        ListNode pre = stack.pop();
        pre.next = pre.next.next;
        return dummy.next;
    }
}
Copy the code