Remove Nth Node From End of List

// class ListNode {
//     int val;
//     ListNode next;
// }

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, Integer n) {
        // Your code goes here
    }
}

Solutions

In order to remove the n-th node from the end of the list, we first need to locate the node right before it.

For example, if our list is [5, 4, 3, 2, 1] and n = 2, then we need to remove the 2nd node from the end with value 2. In order to do so, we first need to locate the node right before it, with value 3.

If we have a pointer to that node current, we can delete node 2 by setting current.next = current.next.next, which removes node 2 from the list (as no nodes point to it).

Here are a 3 solutions to this problem, each of which approach the problem of locating the node right before the n-th node from the end in a different way.

1. Find the Length of the List

The first approach is to traverse the list to find its length. Once we know the length of the list, we can find the node right before the n-th node from the end by traversing length - n - 1 nodes from the head.

public ListNode removeNthFromEnd(ListNode head, int n) {
    // find length
    int length = 0;
    ListNode current = head;
    while (current != null) {
        length++;
        current = current.next;
    }
    
    int target = length - n;
    if (target == 0) {
        return head.next;
    }
    
    current = head;
    for (int i = 0; i < target - 1; i++) {
        current = current.next;
    }
    
    current.next = current.next.next;
    return head;
}

We have to handle the special case when n is equal to the length of the list, which requires removing the head node. This needs to be handled separately because head does not have a node right before it to locate. Instead, when n == length, we can remove the head node by returning head.next directly.

Time Complexity: O(N), where N is the number of nodes in the list. We traverse the list once to find the length of the list, and another time to find the node right before the n-th node from the end. Both traversals take O(N) time.

Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.

2. Use Two Pointers

Instead of traversing the list once to find its length, we can use two pointers, fast and slow that both start at head. To start, fast advances n nodes ahead of slow. Then both pointers advance one node at a time until fast reaches the last node in the list.

At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head, slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // special case: removing head
    if (fast == null) {
        return head.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    slow.next = slow.next.next;
    return head;
}

Like before, we have to handle the special case when n is equal to the length of the list. Since we don't know the length of the list, we can't detect this case by comparing the two values directly. Instead, if fast is None after advancing n nodes, we know that n is equal to the length of the list, and we can remove the head node by returning head.next directly.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head, slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // special case: removing head
    if (fast == null) {
        return head.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    slow.next = slow.next.next;
    return head;
}

Time Complexity: O(N), where N is the number of nodes in the list. The fast pointer first advances n nodes, then both pointers advance together until fast reaches the end. In total, fast traverses N nodes and slow traverses N - n nodes, giving us O(N) time.

Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.

3. Dummy Node

In the two above approaches, we need special logic to handle removing the head node because the head node does not have a node right before it to locate.

We can avoid this special case by introducing a dummy node that points to the head of the list. The dummy node allows us to treat every node, including the head, as if it has a preceding node. With the dummy node established, we can again use the two-pointer approach to find the node right before the n-th node from the end.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // remove nth node from end
    slow.next = slow.next.next;
    return dummy.next;
}

Both the fast and slow pointers start at the dummy node, and like before, fast advances n nodes ahead of slow. Then both pointers advance one node at a time until fast reaches the last node in the list.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // remove nth node from end
    slow.next = slow.next.next;
    return dummy.next;
}

At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next, and return dummy.next as the head of the modified list.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // remove nth node from end
    slow.next = slow.next.next;
    return dummy.next;
}

Removing the Head Node

With the dummy node, when n is equal to the length of the list, slow still points to the dummy node after both the fast and slow pointers finish advancing.

Now, we can remove the head node by setting slow.next = slow.next.next, and return slow.next as the head of the modified list - which is the exact same logic as removing any other node!

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // remove nth node from end
    slow.next = slow.next.next;
    return dummy.next;
}

Implementation

Here's the complete dummy node approach that elegantly handles all edge cases:

public ListNode removeNthFromEnd(ListNode head, int n) {
    // Create dummy node to handle edge case of removing head
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // Move fast pointer n steps ahead to create n-node gap
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // Move both pointers until fast reaches end
    // When fast is at last node, slow will be at node before target
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // Remove the nth node from end by skipping it
    slow.next = slow.next.next;
    
    return dummy.next;  // Return head of modified list
}

Code

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // remove nth node from end
    slow.next = slow.next.next;
    return dummy.next;
}