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;
node = head;
for (int i = 0; i < idx – 1; i++)
node = node->next;
// ListNode* tmp = node->next;
node->next = node->next->next;
// delete tmp;
return head;
}
};
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;
return head;
}
};
Timing:
O(n)