Remove Nth Node From End of List

Medium

Amazon

1 view

Topics:

Linked ListsTwo Pointers

Given the head of a singly linked list, remove the nth node from the end of the list and return its head. You must do this in one pass. The value of n will always be valid (1 <= n <= size of list).

Example 1:

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

(Visually, the linked list 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 2 -> 3 -> 5 after removing the second to last node.)

Example 2:

Input: head = [1], n = 1 Output: []

(Visually, the linked list 1 becomes empty after removing the only node.)

Example 3:

Input: head = [1,2], n = 1 Output: [1]

(Visually, the linked list 1 -> 2 becomes 1 after removing the last node.)

Clarifications:

The number of nodes in the list is guaranteed to be between 1 and 30.
Node values are between 0 and 100.
What should I return if the input list is null? (Assume it is not null given the constraints, but clarify this in a real interview.)
What should I do if n is invalid (e.g., n <= 0 or n > size of list)? (Assume n is always valid, but clarify in a real interview.)

Remove Nth Node From End of List

Medium

Amazon

1 view

Topics:

Linked ListsTwo Pointers

Given the head of a singly linked list, remove the nth node from the end of the list and return its head. You must do this in one pass. The value of n will always be valid (1 <= n <= size of list).

Example 1:

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

(Visually, the linked list 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 2 -> 3 -> 5 after removing the second to last node.)

Example 2:

Input: head = [1], n = 1 Output: []

(Visually, the linked list 1 becomes empty after removing the only node.)

Example 3:

Input: head = [1,2], n = 1 Output: [1]

(Visually, the linked list 1 -> 2 becomes 1 after removing the last node.)

Clarifications:

The number of nodes in the list is guaranteed to be between 1 and 30.
Node values are between 0 and 100.
What should I return if the input list is null? (Assume it is not null given the constraints, but clarify this in a real interview.)
What should I do if n is invalid (e.g., n <= 0 or n > size of list)? (Assume n is always valid, but clarify in a real interview.)

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `n`, and is `n` guaranteed to be a positive integer?
Could the input list be empty, and if so, what should I return?
Is `n` guaranteed to be less than or equal to the length of the linked list?
If the list has only one node, and n is 1, should I return null?
Can I modify the existing list in place, or do I need to create a new list?

Brute Force Solution

Approach

The brute force approach finds the node to remove by first figuring out the total number of nodes in the list. Then, it goes through the list again to find the node that's a certain distance from the beginning, corresponding to the node we want to remove from the end.

Here's how the algorithm would work step-by-step:

First, we need to know how long the list is, so we walk through it and count all the nodes.
Now that we know the total length, we can calculate the position of the node we want to remove, counting from the beginning of the list.
Next, we go back to the beginning of the list.
We walk through the list again, stopping just before the node we want to remove.
We then rearrange the links to skip over the node we want to remove, effectively taking it out of the list.

Code Implementation

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

def remove_nth_from_end_brute_force(head: ListNode, n: int) -> ListNode:
    list_length = 0
    current_node = head

    # Calculate length of the linked list
    while current_node:
        list_length += 1
        current_node = current_node.next

    node_to_remove_index = list_length - n

    # Handle case where the head node needs to be removed
    if node_to_remove_index == 0:
        return head.next

    current_node = head
    # Traverse to node before the node to be removed
    for _ in range(node_to_remove_index - 1):
        current_node = current_node.next

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

    return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once to determine its length, which takes O(n) time, where n is the number of nodes in the list. Then, it iterates through the list again to locate the node preceding the one to be removed, also taking O(n) time. Since these operations are performed sequentially, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The provided algorithm iterates through the linked list a couple of times, but it doesn't create any auxiliary data structures that grow with the size of the input list. It only uses a few constant space variables, such as counters to keep track of the current node and the list length. The amount of extra memory used is independent of the number of nodes (N) in the linked list. Therefore, the space complexity is constant.

Optimal Solution

Approach

The trick is to use two pointers that are a specific distance apart to find the node to remove in one pass. By keeping a fixed gap between them, we can identify the node right before the one we want to remove without knowing the list's length beforehand.

Here's how the algorithm would work step-by-step:

Imagine two runners starting a race together, but one runner gets a head start of 'N' steps.
Let both runners proceed down the list together, maintaining that same 'N' step difference between them.
When the runner in the lead reaches the end of the list, the runner behind is now perfectly positioned 'N' steps from the end.
The runner behind is pointing to the node just before the node we want to remove. Change the pointer of the node behind to skip the node we want to remove.
Take special care for the case where we're asked to remove the first node in the list; adjust the beginning of the list accordingly.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def remove_nth_from_end(head, n):
    leading_pointer = head
    trailing_pointer = head

    # Advance the leading pointer by n steps
    for _ in range(n):
        if not leading_pointer:
            return head
        leading_pointer = leading_pointer.next_node

    # If leading pointer reaches the end first, remove the head
    if not leading_pointer:
        return head.next_node

    # Advance both pointers until leading pointer reaches the end.
    while leading_pointer.next_node:
        leading_pointer = leading_pointer.next_node
        trailing_pointer = trailing_pointer.next_node

    # trailing pointer is now one node before the one to remove
    trailing_pointer.next_node = trailing_pointer.next_node.next_node

    return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers to traverse the linked list. The first pointer moves N steps ahead. Then, both pointers move one step at a time until the first pointer reaches the end of the list. This means that each node in the list is visited at most a constant number of times (twice). Therefore, the time complexity is directly proportional to the number of nodes in the list, denoted as 'n'. Hence, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses two pointers to traverse the linked list. These pointers occupy a constant amount of space, regardless of the linked list's size. No additional data structures like arrays or hash maps are created. Therefore, the auxiliary space complexity is constant, independent of the number of nodes, N, in the linked list.

Edge Cases

Case	How to Handle
Empty list (head is null)	Return null immediately, as there are no nodes to remove.
n is greater than the length of the list	Return the original list without modification, or throw an exception if specified by the prompt.
List has only one node and n is 1	Return null, as removing the only node results in an empty list.
n is equal to the length of the list (removing the head)	Return head.next, effectively making the second node the new head.
List has two nodes and n is 1	Remove the last node and return the head.
List has two nodes and n is 2	Remove the first node (head) and return the second node.
Very large list to ensure algorithm efficiency.	Two-pointer approach maintains O(1) space complexity regardless of list size, and O(N) time.
Integer overflow when calculating list length or positions.	Using appropriate data types (e.g., long) or carefully designed loops avoids overflows.