Problem Statement: Given a linked list, and a number N. Find the Nth node from the end of this linked list and delete it. Return the head of the new modified linked list.

Example 1 : 

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

Output: [1,2,3,5]

Explanation: Refer Below Image

Example 2:

Input: head = [7,6,9,4,13,2,8], n = 6

Output: [7,9,4,13,2,8]

Explanation: Refer Below Image

Example 3:

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

Output: [2,3]

Solution : 

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Naive Approach [Traverse 2 times]

Intuition: 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.

Solution 2: [Efficient] Two pointer Approach

Unlike the above approach, we don’t have to maintain the count value, we can find the nth node just by one traversal by using two pointer approach.

Intuition : 

What if we had to modify the same above approach to work in just one traversal? Let’s see what all information we have here:

1. We have the flexibility of using two-pointers now.
2. We know, that the n-th node from the end is the same as (total nodes – n)th node from start.
3. But, we are not allowed to calculate total nodes, as we can do only one traversal.

What if, one out of the two-pointers is at the nth node from start instead of the end? Will it make anything easier for us?

Yes, with two pointers in hand out of which one is at the n-th node from start, we can just advance both of them till the end simultaneously, once the faster reaches the end, the slower will stand at the n-th node from the end.

Approach : 

1. Take two dummy nodes, who’s next will be pointing to the head.
2. Take another node to store the head, initially,s a dummy node(start), and the next node will be pointing to the head. The reason why we are using this extra dummy node is that there is an edge case. If the node is equal to the length of the LinkedList, then this slow will point to slow’s next→ next. And we can say our dummy start node will be broken and will be connected to the slow next→ next.
3. Start traversing until the fast pointer reaches the nth node.

4. Now start traversing by one step both of the pointers until the fast pointers reach the end.    

5. When the traversal is done, just do the deleting part. Make slow pointers next to the next of the slow pointer to ignore/disconnect the given node.

6. Last, return to the next start.

Dry Run:  We will be taking the first example for the dry run, so, the LinkedList is [1,2,3,4,5] and the node which has to be deleted is 2 from the last. For the first time, fast ptr starts traversing from node 1 and reaches 2, as it traverses for node number 2, then the slow ptr starts increasing one, and as well as the fast ptr until it reaches the end.

• 1st traversal : fast=3, slow=1
• 2nd traversal : fast=4, slow=2
• 3rd traversal : fast=5, slow=3

Now, the slow->next->next will be pointed to the slow->next

So , the new linked list will be [1,2,3,5]

Code : 

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * start = new ListNode();
        start -> next = head;
        ListNode* fast = start;
        ListNode* 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;
        
        return start->next;
    }
};

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode();
        start.next = head;
        ListNode fast = start;
        ListNode 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;
        
        return start.next;
    }
}

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        start = ListNode()
        start.next = head
        fast = start
        slow = start


        for i in range(1, n+1):
            fast = fast.next


        while fast.next != None:
            fast = fast.next
            slow = slow.next


        slow.next = slow.next.next


        return start.next

Time Complexity: O(N)

Space Complexity: O(1)

Special thanks to Upama Dutta and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article