# Delete the nth last node of the linked list

Given a linked list, delete the last n nodes of the list and return to the head node.
For example,
Given a list: 1 - > 2 - > 3 - > 4 - > 5, and n = 2

When the penultimate node is deleted, the linked list becomes 1 - > 2 - > 3 - > 5

Explain:
The n given is always valid.
Try to traverse the implementation once.

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);
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)
length = 0
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);
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);
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)
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);
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;
}```

Keywords: Java Python

Added by jplock on Mon, 06 Apr 2020 00:50:32 +0300