Remove Nth Node From End of List
head of a linked list, remove the
nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Input: head = , n = 1
Input: head = [1,2], n = 1
- The number of nodes in the list is
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
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).