Leetcode 19. Remove Nth Node From End of List

Problem

Leetcode 19 - Remove Nth Node From End of List

Example:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

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

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

Approach

We can use two-pointer to solve this problem

• move right pointer by n steps
• have left pointer start at dummy where dummy.next = head
• move left pointer and right pointer by 1 until right pointer is None
• make left.next = left.next.next so we’re skipping n’th node

Visualization of the Approach:

head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
dummy -> 1 -> 2 -> 3 -> 4 -> 5
 l       r

get right pointer
dummy -> 1 -> 2 -> 3 -> 4 -> 5
 l                 r

start shifting left and right until right is None
dummy -> 1 -> 2 -> 3 -> 4 -> 5
         l              r

dummy -> 1 -> 2 -> 3 -> 4 -> 5
              l              r
        
dummy -> 1 -> 2 -> 3 -> 4 -> 5
                   l           

Remove the left.next node by skipping
dummy -> 1 -> 2 -> 3 -> 5

Return dummy.next

Here is the Python code for the solution:

class Solution:
    def removeNthFromend(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1
        
        while right:
            left = left.next
            right = right.next
        
        left.next = left.next.next
        return dummy.next    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$