Remove Nth Node From End OF List

Problem

Given a reference head of type ListNode that is the head node of a singly linked list and an integer n, write a function that removes the n-th node from the end of the list and returns the head of the modified list.

Note: n is guaranteed to be between 1 and the length of the list. If n is the length of the list, the head of the list should be removed.

Example 1

Input: n = 2

Output:

Explanation: The 2nd to last node is removed from the list.

Example 2

Input: n = 5

Output:

Explanation: The 5th to last node is the head node, so it is removed.

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.

def removeNthFromEnd(head, n):
    # find length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    target = length - n
    if target == 0:
        return head.next
    
    current = head
    for _ in range(target - 1):
        current = current.next
    
    current.next = current.next.next
    return 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;
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // find length
    length := 0
    current := head
    for current != nil {
        length++
        current = current.Next
    }
    
    target := length - n
    if target == 0 {
        return head.Next
    }
    
    current = head
    for i := 0; i < target-1; i++ {
        current = current.Next
    }
    
    current.Next = current.Next.Next
    return head
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // find length
    let length: number = 0;
    let current: ListNode | null = head;
    while (current) {
        length++;
        current = current.next;
    }
    
    let target: number = length - n;
    if (target === 0) {
        return head!.next;
    }
    
    current = head;
    for (let 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.

def removeNthFromEnd(head, n):
    fast = slow = head
    for _ in range(n):
        fast = fast.next
    
    # special case: removing head
    if not fast:
        return head.next
    
    while fast.next:
        fast = fast.next
        slow = slow.next
    
    slow.next = slow.next.next
    return head

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;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    fast := head
    slow := head
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    
    // special case: removing head
    if fast == nil {
        return head.Next
    }
    
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    slow.Next = slow.Next.Next
    return head
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let fast: ListNode | null = head, slow: ListNode | null = head;
    for (let i = 0; i < n; i++) {
        fast = fast!.next;
    }
    
    // special case: removing head
    if (!fast) {
        return head!.next;
    }
    
    while (fast.next) {
        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.

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.

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head
    
    fast, slow = dummy, dummy
    for _ in range(n):
        fast = fast.next
    
    while fast.next:
        fast = fast.next
        slow = slow.next
    
    # remove nth node from end
    slow.next = slow.next.next
    return dummy.next

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;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    
    fast, slow := dummy, dummy
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    // remove nth node from end
    slow.Next = slow.Next.Next
    return dummy.Next
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let dummy = new ListNode(0);
    dummy.next = head;
    
    let fast: ListNode | null = dummy, slow: ListNode | null = dummy;
    for (let i = 0; i < n; i++) {
        fast = fast!.next;
    }
    
    while (fast!.next) {
        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.

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.

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!

Implementation

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

Code

To construct the linked list that is used in the animation below, provide a list of integers nodes. Each integer in nodes is used as the value of a node in the linked list, and the order of the integers in the list will be the order of the nodes in the linked list.

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.