19.Remove_Nth_Node_From_End_of_List(Medium).md

19. Remove Nth Node From End of List (Medium)

Date and Time: Jul 31, 2024, 17:53 (EST)

Link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

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]

Constraints:

• The number of nodes in the list is sz.

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

Walk-through:

1. Set a dummy node dummy = tail = ListNode(0, head) and set right to be n positions away from head by using while loop to advance right.

2. We move tail and right together until right is None, so we know tail.next is the node we want to remove. And we just link tail.next = tail.next.next to skip the node we need to remove.

Python Solution:

# 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]:
        # Follow the hint, we use two pointers and the gap between them is n + 1, we can do that by creating a dummy node
        dummy = tail = ListNode(0, head)
        right = head
        # We first advance the right pointer
        while n > 0 and right:
            right = right.next
            n -= 1
        while right:
            tail, right = tail.next, right.next
        tail.next = tail.next.next
        return dummy.next

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

Java Solution:

C++ Solution:

Runtime and Memory comparison

Language	Runtime	Memory
Python3	ms	MB
Java	ms	MB
C++	ms	MB