Delete the nth last node of the linked list

Here we refer to Website The algorithm of solving the problem.

Method 1

It should be noted that to delete the nth last node is actually to delete the (L-n+1) node. Here, l represents the length of the entire list. We can first traverse the list once, calculate the length of the list, then find the node according to L-n+1, and do the deletion operation.

Java

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;/// Ensure that the operation of the head node can be deleted
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }

Python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        length = 0
        first = head
        while (first):
            length = length + 1
            first = first.next
        length = length - n
        first = dummy
        while (length > 0):
            length = length - 1
            first = first.next
        will_delete = first.next
        first.next = will_delete.next
        del (will_delete)
        return dummy.next

C++

ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode dummy = ListNode(0);
        dummy.next = head;
        int length = 0;
        ListNode* first = head;
        while(first!=NULL)
        {
            length++;
            first = first->next;
        }
        length -= n;
        first = &dummy;
        while(length>0)
        {
            length--;
            first = first->next;
        }
        ListNode *will_delete = first->next;
        first->next = will_delete->next;
        delete(will_delete);
        return dummy.next;
    }

Method two

We can use two pointers, first and second. In the initial state, both pointers point to the head node, then move the first pointer to move n nodes backward, so that N nodes are separated between the first and second pointers, and then move the first and second pointers at the same time (similar to the translation operation), until the first pointer points to the tail node, at this time, the second pointer is just OK, point to the nth to last node and delete it. This algorithm is very clever and likes it very much.

Java

    public ListNode removeNthFromEnd_2(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

Python

    def removeNthFromEnd_2(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy
        for i in range(n + 1):
            first = first.next
        while (first):
            first = first.next
            second = second.next
        will_delete = second.next
        second.next = will_delete.next
        del (will_delete)
        return dummy.next

C++

 ListNode* removeNthFromEnd_2(ListNode* head, int n)
    {
        ListNode dummy(0);
        dummy.next=head;
        ListNode* first=&dummy;
        ListNode* second=&dummy;
        for(int i=0;i<=n;i++)
        {
            first=first->next;
        }
        while(first!=NULL)
        {
            first=first->next;
            second=second->next;
        }
        ListNode* will_delete = second->next;
        second->next=will_delete->next;
        delete(will_delete);
        return dummy.next;
    }