Data Structures & Algorithms in Java – Linked List – Remove Nth Node from the last

Problem:

Given a linked list , remove the nth node from the end of the list

For example,

For the linked list [1,2,3,4,5] and the number n = 3

Remove the 3rd element from the last which is 3.

So the final list is [1,2,4,5]

Try out the solution here:

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Solution:

Hint:

• Find the length of the linked list and subtract “n” from the length. This will give you the position of the previous node to the node to be deleted from the beginning. Adjust pointers accordingly.
• Have two pointers point to the first node , move one of them to n positions from the first node. Then move both pointers together until the pointer in nth position reaches the end. This gives the previous node to the one to be deleted. Adjust next pointer accordingly.

Explanation:

Two pass approach:

You can solve this problem either in two passes or one pass.

Let’s look into the two pass approach.

In the first pass you navigate the linked list from start to end and find out the length.

Subtract the given number from this length.

This will give the position of the previous node of the node to be deleted.

Point the next pointer of the previous node to the next to next pointer of the previous node.

One pass approach:

In one pass approach , use two pointers.

Point both of them to the first node.

Move one of them to n positions from the first node.

Now the two pointers are “n” nodes apart.

Move both the pointers together until the pointer which was in “n” th position reaches the end.

Now both the pointers are still “n” nodes apart and the position of the first pointer gives the position of the previous node of the node to be deleted.

Point the next node of the previous node to the next to next node of the previous node. So the node to be deleted is ignored in the linked list chain.

Both in the one pass and two passes approach , we need to create a dummy list node initially whose next pointer points to the head.

This is because , if the nth node from the last is the first node then you need “a previous node” whose next pointer can be made to point to the next node of the first node according to the two algorithms.

Finally you will return the next node of the previous node which points to the head of the final linked list.

ALGORITHM(Two passes):

STEP 1: Initialize a variable to represent the length of the linked list

STEP 2: Initialize a list node “count” to navigate the linked list for calculating the length

STEP 3: Traverse the linked list using “count” pointer and find out the length of the linked list

STEP 4: Subtract the given number from the length. This gives the position of the previous node of the node to be deleted

STEP 5: Create an empty previous pointer whose next points to the head.

STEP 6: Create a current pointer which points to the previous pointer. This will be used to go to the previous position of the node to be deleted.

STEP 7: Using the current pointer move for the number of times of the calculated length . This lands the pointer in the previous node to the node to be deleted.

STEP 8: Make the next of current pointer point to its next to next node. This leaves the node to be deleted from the linked list chain.

Here is the code:

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        
        int length = 0;
        
    
        ListNode count = head;
        
        while(count != null){
            
            
            length++;
            
            count = count.next;
        }
        
        length = length - n;
        
        
        ListNode prev = new ListNode();
        
        prev.next = head;
        
        ListNode curr = prev;
        
        for(int i = 0;i<length;i++){
            
            curr = curr.next;
        }
        
        
        
        curr.next = curr.next.next;
        
        
        
        return prev.next;
        
    }
}

ALGORITHM (One pass approach):

STEP 1: Create a dummy previous pointer node whose next points to the head

STEP 2: Create two pointers both of which point to the previous dummy node.

STEP 3: Move the second pointer of the previous step to “n” positions from the first node. So the distance between the first pointer and the second pointer is “n”.

STEP 4: Now move both the pointers one by one until the second pointer reaches the end of the linked list. At this point , the first pointer points to the previous node of the node to be deleted

STEP 5: Point the next node of the first pointer to its next to next node. This leaves out the node to be deleted.

Here is the code:

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        
        
        
        ListNode prev = new ListNode();
        
        prev.next = head;
        
        
        
        
        
        
        ListNode first = prev;
        
        ListNode second = prev;
        
        for(int i = 0;i<=n;i++){
            
            second = second.next;
        }
        
        
        while(second!=null){
            
            first = first.next;
            
            second = second.next;
        }
        
        
        first.next = first.next.next;
        
        
        
        return prev.next;
        
    }
}

Time complexity of both the algorithms is O(n)

Space complexity is O(1) since we don’t use any space which grows in proportion to the input size.

That’s it!