algoadvance

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example:

Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Clarifying Questions

1. Is it guaranteed that n is always valid, i.e., 1 <= n <= sz?
   • Yes, based on the constraints.
2. Should the function return the new head of the list or just modify the list in place?
   • The function should return the new head of the list.
3. Can I assume that the list contains only integers?
   • Yes, based on the problem statement.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # Create a dummy node to handle edge cases more easily
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
    
    # Move first pointer so that there is a gap of n nodes between first and second
    for _ in range(n + 1):
        first = first.next

    # Move both pointers until first reaches the end
    while first is not None:
        first = first.next
        second = second.next
    
    # Remove the nth node from end
    second.next = second.next.next
    
    # Return the new head
    return dummy.next

Strategy

1. Use a Dummy Node:
   • Introduce a dummy node that points to the head of the list. This helps in handling edge cases where the head might be removed.
2. Two Pointers Technique:
   • Utilize two pointers (first and second).
   • First, advance the first pointer by n + 1 steps from the dummy node. This ensures that the gap between first and second is n nodes.
   • Move both pointers one step at a time until first pointer reaches the end.
   • Now, second pointer is at the node right before the node to be removed.
3. Remove the Node:
   • Change the next pointer of the second node to skip the node to be removed.
4. Return the New Head:
   • Return dummy.next which points to the updated head of the list.

Time Complexity

• Time Complexity: O(L) where L is the number of nodes in the linked list. We traverse the list once.
• Space Complexity: O(1) because we only use a fixed amount of extra space (pointers).

This approach ensures that we efficiently remove the nth node from the end of the list with a single pass through the list.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?