# 19. Remove Nth Node From End of List

Description:

https://leetcode.com/problems/remove-nth-node-from-end-of-list/#/description

Boundary:

n == length: delete head

n > length: delete nothing

Algorithm:

My method:

Count to find length of the list -> get index of the node in front of the deleted node -> delete (beats 66%)

The optimized method:

Two pointers: pre and pos

Code:

My Code:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* node = head;
int length = 0;
while (node != NULL)
{
length++;
node = node->next;
};
if (n > length)
return NULL;
if (n == length) return head->next;

int idx = length – n;
for (int i = 0; i < idx – 1; i++)
node = node->next;

// ListNode* tmp = node->next;
node->next = node->next->next;
// delete tmp;
}
};

Optimized Code:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* pre = head;
ListNode* pos = head;

while (pre != NULL)
{
if(n < 0)
{
pos = pos -> next;
}
pre = pre -> next;
n–;
};
if (n == 0) return head-> next;
if (n > 0) return NULL;

pos -> next = pos -> next -> next;