# Remove Nth Node From End of List — Day 107(Python)

3 min readJan 26, 2022

--

Today we will be working on the LinkedList problem. Let’s look into the problem statement.

19. 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`.
• `1 <= sz <= 30`
• `0 <= Node.val <= 100`
• `1 <= n <= sz`

Follow up: Could you do this in one pass?

One way to solve this problem is to find at what position we want to remove the node from. To identify that position, first, find the length of the linked list, then subtract N from the length of the linked list.

After finding the position, we will traverse through the linked list and then delete the node in that position. We will use 3 variables that point to the previous node, current node, and next node. Once the current node reaches the required position, we will point the previous node to the next node, thus removing the current node.

Let us look into the code.

`# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def length_ll(self, head):        length_of_linkedlist = 0        while(head):            length_of_linkedlist += 1            head = head.next        return length_of_linkedlist        def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        length_of_linkedlist = self.length_ll(head)        prev, curr = None, head        position_to_remove = length_of_linkedlist - n        if(length_of_linkedlist == 1 and n == 1 or position_to_remove == 0):            return head.next        while(curr):            nex = curr.next            if(position_to_remove == 0):                prev.next = nex                break            else:                prev = curr                curr = nex                position_to_remove -= 1        return head`

Complexity Analysis

Time Complexity

We are traversing through the linked list twice; once to find the length of the linked list and second to remove the node. The time complexity is O(N) where N is the length of the Linked list.

Space Complexity

We are not using any extra space and hence space complexity is O(1).

How can we solve this problem in one pass? I had to look into the solution to understand that having two-pointers are considered as one pass.

Pointer 1 will move until we reach n. Once pointer 1 reaches n, we will start pointer 2 until pointer 1 reaches the end of the linked list. The node which pointer 2 points at, is the node that needs to be removed.

`# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        if head.next is None:            return None        fast,slow=head,head        for i in range(n):            fast=fast.next        if not fast:            return head.next        while fast.next:            slow=slow.next            fast=fast.next        if n==1:            slow.next=None        else:            slow.next=slow.next.next        return head`

Complexity Analysis

Time Complexity

We are traversing through the linked list using two pointers, hence time complexity is O(N).

Space Complexity

We are not using any extra space and hence space complexity is O(1).