LeetCode 19 - Remove Nth Node From End of List - Python

 

Question:

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]

Answer:

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Approach:

1. Calculate the size of the Single Linked List. We need to travel to the prev node of the node to be removed thus we perform reduce size by n
2. If the node to be removed is the first node (size == 0) then we can simply return the next node of head since it will be null if the list has only one node.
3. Traverse till the prev node using a loop again
4. Skip the next node by linking the prev node to the next of next node. If not present, assign null.
5. Finally return the head.

Time complexity:

O(n)

Space complexity:

O(1)

Code:

# 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]:
        length = self.findLength(head)
        i, traverseTill = 0, length - n - 1
        if traverseTill == -1:
            return head.next
        curr = head
        while i < traverseTill:
            curr = curr.next
            i += 1
        curr.next = curr.next.next
        return head

    def findLength(self, head):
        count = 0
        if head is None:
            return count
        curr = head
        while curr is not None:
            count += 1
            curr = curr.next
        return count