LeetCode – 19. Delete the NTH node from the list

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Delete the NTH node from a linked list

If you are given a linked list, delete the last NTH node from the list. For example, delete the second last node from the list.

There is an advanced requirement in the problem: the detachment list should be scanned once.

Answer:

The most obvious way: Because the list only scans from start node to the end node, and unable to retrieve the length of the list before scanning, therefore, can only scan it again, count list altogether how many nodes, assuming that node number is l, from bottom to remove the NTH node, then by the second time, will be the first l – n + 1 node deleted.

This method scans the list twice and does not meet the advanced requirements of the problem. If we can only scan the list once, we need to hold a variable pointing to the previous node from the NTH to the last node when we reach the last node (because deleting a node needs to be done on the previous node, that is, moving the next pointer from the previous node to the next node, This removes the current node from the list. Because we do not know which one node is the last node, every seconds to a node, could be the last node, therefore, we need a variable, always slower than the current scan n nodes, so, when the scanning to the last node, this variable points to is to delete the node before a node, Then delete it.

Note that we also need to consider the case where the length of the list is less than n, in which case we don’t need to operate on the list.

In addition, to reduce loop and null pointer judgments, add a node at the front of the list as an aid.

Final code:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode f = head;
        ListNode s = dummy;
        for (int i = 0; i < n; ++i) {
            f = f.next;
        }
        while(f ! =null) {
            f = f.next;
            s = s.next;
        }
        s.next = s.next.next;
        returndummy.next; }}Copy the code