Remove Nth Node from the End of the Linked List

Learn to play with Linked List by solving this DSA problem in Java. This is LeetCode problem 19.

We are given a linked list head and an integer n and we need to remove the nth node of this list from the end or we can say the (L - n + 1)th node from the start, where L is the size of the list.

To solve this problem we will use the two-pointer technique, which is also called the fast and slow pointer method, which allows us to remove the nth node from the end in one pass, meaning L iterations.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

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

    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

We use a dummy node to handle edge cases like deleting the head and to always have a pointer to the node before the one to delete. It ensures safe, uniform logic and lets us return dummy.next as the updated head.

We can understand this solution by considering an example. Let's say the size of the given list is 8 and n = 2. It means we need to remove the 2nd node from the end and the 7th node from the start.

We moved fast 2 nodes ahead using the first for loop and when the while loop runs, fast reaches null and slow reaches the 6th node, which means we are just one node before the one that needs to be removed, and finally it is removed by the code below.

slow.next = slow.next.next;

So this is the two-pointer technique to remove the nth node from the end of a linked list and the time complexity of this solution is O(L).

I hope you enjoyed solving this problem with me, understood the two-pointer technique and why we use a dummy node, and found this post helpful in building your DSA skills.

Thanks for reading! 🤝 Happy Coding! ✨