Remove nth node from the end of Linked List

Given a linked list with N number of nodes. Our task is to find the Nth node from the end of this linked list and delete it. Return the head of the new modified linked list.

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

Output: [1,2,3,5]

Approach

Naive Approach

We can traverse through the Linked List while maintaining a count of nodes, let’s say in the variable count, and then traversing for the 2nd time for (n – count) nodes to get to the nth node of the list.

Efficient Approach (1 Pass)

We will use two pointer approach. Create a slow and fast pointer such that the difference between them is n. The slow pointer will be at the start of list and the fast pointer will be pointing to n nodes ahead of slow pointer. This will ensure when we advance both the nodes, the difference between them will always be n. When the fast node reaches the last node, the slow pointer’s next node will be our target node that we want to delete. This is because we have maintained difference of n nodes between slow and fast node.

We could point the slow and fast pointer to head and start the processing, but we want to take care of use case where list might be empty. To take care of such cases we will create a dummy node that points to head and assign the slow and fast pointer starting from dummy node.

1. Create one dummy node and point it to head.
2. Take a slow and fast node and point it to dummy node.
3. Traverse fast node n time.
4. Now traverse both pointers slow and fast such that fast reaches the end of list.
5. When the traversal is done, delete the node using slow’s reference.
6. Lastly, return the dummy node’s next which is the head of linked list.

Complexity

• Time Complexity: O(N), n is the total number of nodes in the linked list.
• Space Complexity : O(1)

Code

# Java Code

class LinkedListRemoveNthFromEnd {

    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    Node head;

    public LinkedListRemoveNthFromEnd() {
        this.head = null;
    }

    // Method to add a new node to the end of the linked list
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Method to display the elements of the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // Method to remove the Nth node from the end of the linked list
    public void removeNthFromEnd(int n) {
        Node start = new Node(0);
        start.next = head;
        Node fast = start;
        Node slow = start;
        for (int i = 1; i <= n; ++i) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        head = start.next; // Update the head if necessary
    }

    public static void main(String[] args) {
        LinkedListRemoveNthFromEnd list = new LinkedListRemoveNthFromEnd();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append(4);
        list.append(5);
        System.out.println("Linked List:");
        list.display();
        int n = 2;
        list.removeNthFromEnd(n);
        System.out.println("Linked List after removing the " + n + "th node from the end:");
        list.display();
    }
}

Output

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null
Linked List after removing the 2th node from the end:
1 -> 2 -> 3 -> 5 -> null