Remove Nth Node from List End

Given a linked list, remove the nth node from the end of list and return its head.

For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
* If n is greater than the size of the list, remove the first node of the list.

 

Try doing it using constant additional space.

Approach: Use one pointer first to move to the nth node and then start one from the start and other from the nth node. Once the nth node pointer reaches the end, the other one will be at the nth from the last which can be deleted easily.

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

ListNode* Solution::removeNthFromEnd(ListNode* head, int n) { if(head == NULL){ return NULL; } ListNode *t1, *t2, *prev; int count = 0; t1 = head; t2 = head; while(t1 && count < n){ count++; t1 = t1->next; } //if already reached the end, then head needs to be moved forward if(t1 == NULL){ head = head->next; return head; } //else move till we reach end in the first pointer while(t1){ prev = t2; t2 = t2->next; t1 = t1->next; } //update the previous pointer prev->next = t2->next; return head; }