19. Remove Nth Node From End of List

MediumLeetCode

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

How to solve the problem

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]:
        # Fast and slow pointer
        dummyhead = ListNode(0, head)
        fast = dummyhead
        slow = dummyhead

        for _ in range(n): # Let fast pointer move n step first
            fast = fast.next

        while(fast.next != None): # Move slow and fast pointer simultaneously
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next # Let node(n-1) point to node(n+1)
        return dummyhead.next

Complexity

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