Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,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 <= 300 <= Node.val <= 1001 <= n <= sz
Algorithm -
A one pass solution can be done using two pointers. Move one pointer fast → n+1 places forward, to maintain a gap of n between the two pointers and then move both at the same speed. Finally, when the fast pointer reaches the end, the slow pointer will be n+1 places behind — just the right spot for it to be able to delete the next node.
Added comments for each step in the code, please do one pass tracing using pen and paper for better understanding.
Complexity- Both time and space is O(n).
