19. Remove Nth Node From End of List

• python3

Problem

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?

Pseudocode

0. If you move n steps in a linked list, the remaining length is the total length minus n. This allows you to determine the distance needed to reach the node that needs to be deleted.
1. Create two pointers.
2. Move the first pointer n steps forward, then move both pointers together until the first pointer reaches the second-to-last node.
3. Delete the node that the second pointer's next reference points to.
4. Return the linked list.

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]:
        
        first = head
        second = head

        for _ in range(n):
            first = first.next
        
        if not first:
            return head.next
        
        while first.next:
            first = first.next
            second = second.next
        
        second.next = second.next.next

        return head

Result

• Time Complexity : O(n)
• Space Complexity : O(1)