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

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 = 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 <= 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.

# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if(length_of_linkedlist == 1 and n == 1 or position_to_remove == 0):
while(curr):
nex = curr.next
if(position_to_remove == 0):
prev.next = nex
break
else:
prev = curr
curr = nex
position_to_remove -= 1

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.

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