# Remove Nth Node From End of List

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 = 2Output: [1,2,3,5]`

Example 2:

`Input: head = [1], n = 1Output: []`

Example 3:

`Input: head = [1,2], n = 1Output: [1]`

Constraints:

• The number of nodes in the list is `sz`.

Approach 1:

2 pointer approach

We keep a ptr1 which traverses the linked list and on reaching the nth element we stop the ptr1 from moving. And this instant we start another pointer ptr2, now both of the pointer move together . When ptr1 reaches the last node the pointer node will be at at previous node of the nth node from end, so now we can easily delete that node .

Note that an additional node is used to point to the head so that could deal with all edge cases including only 1 node in the linked list.

`class Solution(object):    def removeNthFromEnd(self, head, n):        inter,inter.next=ListNode(0),head        head,cnt=inter,0        ptr1,ptr2=head,head        while(cnt!=n):            cnt+=1            ptr1=ptr1.next           while(ptr1.next):            ptr1=ptr1.next            ptr2=ptr2.next        ptr2.next=ptr2.next.next        return (head.next)`

Time: O(n)

Space :O(1)

Approach 2 :

2 pass solution

Here we traverse the linked list once and then count total number of nodes in the linked list and then, find the position of the nth node from end , with respect to the beginning by, total nodes — (n-1).

`class Solution(object):    def removeNthFromEnd(self, head, n):        ptr1=head        cnt=0        while(ptr1):            cnt+=1            ptr1=ptr1.next        if cnt-n==0:            return head.next        val=0        ptr2=head        while(val!=cnt-n-1):            val+=1            ptr2=ptr2.next        ptr2.next=ptr2.next.next        return head`

Time: O(n)

Space :O(1)

Approach 3:

Recursive

On reaching the end of the linked list the index starting from end is returned to the previous caller
which helps in determining the nth node from the end.

`class Solution(object):    def removeNthFromEnd(self, head, n):        def rec(curr,n):            if not curr:                return -1            ind=rec(curr.next,n)+1            if ind ==n:                curr.next=curr.next.next            return ind         inter=ListNode(0)        inter.next=head        head=inter        rec(head,n)        return inter.next`

Time:O(n)
Spcae:O(n)

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.

## More from Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.