LL 11 - Remove Nth node from the back of the Linked List

Problem

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

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

Solution

Brute force approach

We must remove the nth node from the end. To achieve this, we must determine the index of this specific node from the beginning. To do so, we first calculate the total number of nodes and subtract 'n' from it to obtain the index of the target node, which is (total nodes - n).

Deleting a node from a linked list involves updating the pointers. To delete a node, our pointer should be positioned just before the target node.

If temp points to the node before the target, then we can delete the target node by using...

temp.next = temp.next.next

Note: This method is not valid for deleting the first node.

Here we iterate through the linked list twice. The first iteration is to determine the length, and the second iteration is for deletion.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;

        ListNode temp = head;

        while(temp!=null){
            temp = temp.next;
            count+=1;
        }

        //Important check
        if(count==n) return head.next;

        temp = head;

        // Traverse to the node just before the one to delete
        for(int i=0; i<(count-n-1); i++){
            temp = temp.next;
        }

        // No need add any null check first and last node checks already done
        temp.next = temp.next.next;

        return head;
    }
}

Optimal Approach (Slow & Fast pointer)

This method bears resemblance to the brute force approach, but it accomplishes deletion in a single iteration. It employs fast and slow pointers. At any given moment, the fast pointer advances by n nodes ahead. Initially, we move the fast pointer by n nodes, while the slow pointer points to the head. If the fast pointer points to null after n steps, it indicates the need to delete the first node; otherwise, the process continues. Subsequently, we move both pointers until the fast pointer reaches the last node. Once the fast pointer reaches the last node, it signifies that the slow pointer points to the node just before the target. Consequently, we delete the target node using the slow pointer and return the head.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;

        ListNode fast = head;
        ListNode slow = head;

        for(int i=0; i<n; i++){
            fast = fast.next;
        }

         //Important check
        if(fast==null) return head.next;

        // Traverse to the node just before the one to delete
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return head;
    }
}