19. Remove Nth Node From End of List

Medium

Description

Given the head of a linked list, remove the n^th 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?

Solutions

Approach: Fast and Slow pointers

Time complexity: \(O(n)\)

Space complexity: \(O(1)\)

Way 1:

Algorithm 1

We define two pointers fast and slow,both initially pointing to the dummy head node of the linked list.

Next, thefastpointer moves forward n steps first, thenfastand slow pointers move forward together until thefastpointer reaches the end of the linked list. At this point, the node pointed to by slow next is the predecessor of the n-th node from the end, and we can delete it.

The time complexity is 𝑂(𝑛) where 𝑛 is the length of the linked list. The space complexity is 𝑂(1).

Python

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        #Create a dummy node to handle edge cases
        dummy = ListNode(0,head)

        #Intialize pointer fast and slow
        slow = fast = head

        #Move fast pointer n nodes ahead
        for _ in range(n):
            fast = fast.next

        #Move both pointers until fast reaches end
        while fast.next:
            slow = slow.next
            fast = fast.next

        #Remove the nth node from the end
        slow.next = slow.next.next

        return dummy.next

equivalency

dummy = ListNode(0)
dummy.next = head
        ||
        ||
        ||
dummy = ListNode(0,head)

Approach: Simulation

Time complexity: \(O(n)\)

Space complexity: \(O(1)\)

Way 2:

Algorithm 2

Python

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        #Calculate length
        tail , length = head, 0
        while tail:
            length+=1
            tail = tail.next

        #Use a dummy node to handle edge cases, such as removing the head of the list.
        dummy = ListNode(0, head)
        curr = dummy

        #Find the node just before the one we want to remove
        for _ in range(length-n):
            curr = curr.next

        #Remove the connection(nth node from the end)
        if curr.next:
            curr.next = curr.next.next

        return dummy.next