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

Photo by Anne Nygård on Unsplash

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.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class 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 = next
class 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).