Given a linked list, remove the n-th node from the end of list and return its head.
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: Given n will always be valid.
Naive solution
First, we need to get the length of the link list, the time complexity will be $O(N)$, we can not avoid this step, so this is also the best time complexity.
Given the length of link list, remove the n-th node will be easy if we find the node at pos length-n.
Note a dummy node will make the code cleaner.
classSolution { public: ListNode* removeNthFromEnd(ListNode* head, int n){ ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* cur = head; int len = 0; while(cur) { cur = cur->next; len++; } len -= n; cur = dummy; while(len > 0) { cur = cur->next; len--; } cur->next = cur->next->next; return dummy->next; } };
Approach with two pointers
This is a clever approach, if we use two pivot pointers, their distance is n+1. Then if we move the tail forward to the end of linklist, the prev will be the pointer whose next can be deleted!