**source:**https://leetcode.com/problems/remove-nth-node-from-end-of-list/**C/C++**

**Solution to LeetCode**problem

**19**.

**Remove Nth Node From End of List**.

## Problem

Given the `head`

of a linked list, remove the `n`

node from the end of the list and return its head.^{th}

## Examples

**Example 1:**

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

Output:[1,2,3,4,5]

**Example 2:**

Input:head = [1], n = 1

Output:[]

**Example 3:**

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

Output:[1]

## Constraints

- The number of nodes in the list is
`sz`

. `1 <= sz <= 30`

`0 <= Node.val <= 100`

`1 <= n <= sz`

**Follow up**: Could you do this in one pass?

## Solution

We will use a variation of the “Tortoise and Hare” (Floyd’s) algorithm that is used to find cycles in a list of nodes.

- We initialize two pointer at the head node.
- We move one of them
`n`

times. - Then we start moving both at the same time, when the firstone arrives to the end node (when
`pointer_1->next == nullptr`

) then we know that the second pointer is right before the node we want to delete. - Then we just re-assign the
`pointer_2->next`

to`pointer_1_node->next->next`

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* p1 = head;
ListNode* p2 = head;
int i=0;
while (p1->next && i<n) {
p1 = p1->next;
i++;
}
if (i<n)
return head->next;
while(p1->next) {
p1 = p1->next;
p2 = p2->next;
}
p2->next = p2->next->next;
return head;
}
};