GeetCode Hub

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?

# 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: ListNode, n: int) -> ListNode: if not head: return head p1 = p2 = head for _ in range(n): # move p1 (n) times p1 = p1.next while p1 and p1.next: p2 = p2.next p1 = p1.next if p1: # p2 is the parent of to-be-deleted node p2.next = p2.next.next else: # unless p1 is null in which case head is to be removed! head = head.next return head

The main concept to remember in this question is how we can use two pointers, i.e slow and fast pointers, to find the node that needs to be deleted. Once that is found then it is an easy task to delete the node.

 

Time Complexity: O(n)

Space Complexity: O(1)