LeetCode Remove Nth Node From End Of The List Solution

The following article is a solution that aims to solve mostly the LeetCode problem number 19 Remove Nth Node From End Of The List Solution.

Problem

Definitions: Given the head of a linked list, remove the n^th node from the end of the list and return list’s head.

LeetCode provides us also with a few graphical examples. However, the definition is quite clear, and there is not much that we can add to it.

Constrains

Although, LeetCode problem sets certain constrains, none of them will be very critical and limiting. These constrains are:

• 1 <= number of nodes <= 30
• 0 <= Node.val <= 100
• 1 <= n <= number of nodes

A brief look at the constraints should give us straightforward edge cases.

The first edge case should be a linked list with only one element and demand the removal of the first element from the end of the linked list. Basically, we should return NULL.

A second edge case is very similar; we will have a small number of nodes, let’s say two, and we should remove the first or second element from the end. We should get back a linked list of the maximum length of one element for the second edge case.

Any other case will lead towards returning a list of length two or more elements.

ListNode class

While ListNode class is not important, I will still rather keep the reference for the ListNode class code here:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode() {}

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

Remove N-th Node From End Of The List Problem Solution

First of all, I will provide a clean code for the solution so you can go through it. And in case you will have doubts or questions, you can read further. Then, below the answer, I will go through the code and explain parts of the code in greater detail.

Here is a clean code for LeetCode’s Remove N-th Node From End Of The List solution:

public class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummyNode = new ListNode(0);

        dummyNode.next = head;

        ListNode slow = dummyNode;
        ListNode fast = dummyNode;

        // Move fast pointer in front of slow, so the gap between slow and fast pointer becomes n.
        while (n > 0) {
             fast = fast.next;
             n--;
        }

        // You have created window between slow and fast pointer.
        // Move the window on the end of the linked list and maintain the gap.
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;

        return dummyNode.next;
    }
}

Do you understand the solution?

Let’s take a deeper look into the solution.

Solution Explanation

Note to remember: Good advice – always, you will need a dummy node when you have to remove an element in the linked list.

on the beginning, we will “hoist” a small trick where we connect head ListNode to a dummy node. The role of this dummy node will be only to keep a Java reference on the method returnable head node.

I will use an example from the LeetCode page and use a linked list node with five elements for better clarity. Element for removal from the end of the linked list will be the second from the back of the linked list.

ListNode dummyNode = new ListNode(0);
// dummyNode -> NULL
dummyNode.next = head;
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Now, we will use a trick with slow and fast pointer. Let’s assign two new nodes, slow and fast, reference to dummy node .

ListNode slow = dummyNode;
// slow --> dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
ListNode fast = dummyNode;
// fast --> dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Right now everything is ready for our little trick:

ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode slow = dummyNode;
ListNode fast = dummyNode;

What we want is to create a gap between slow and fast node with the size of the element we want to remove from the linked list end. We will visualize it better right away. But until then, we should realize that we want to create a window of size n. It will help us, when sliding towards the end, make a border on which we will find the element we want to remove.

Let’s loop fast pointer n-times sideways:

while (n > 0) {
     fast = fast.next;
     n--;
}

//     F
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//              F
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                   F
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Now we have a two pointers, slow and fast, separated by the length of n.

All we have to do is move the window created by two pointers, slow and fast, to the end of the linked list.

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

// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//              S
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                        F
//              |<- gap ->|

// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                   S
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                             F
//                   |<- gap ->|

// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                        S
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                                  F
//                        |<- gap ->|

We see that now we moved our window created by slow and fast pointer on the end of linked list.

The only thing left is to skip the desired node after slow pointer.

slow.next = slow.next.next;
// dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
//                        S <- reassigning the node
// dummyNode -> 1 -> 2 -> 3 -> 5 -> NULL

Finally we can return the reference on head from dummy node:

//  returning the head of helping dummy node
return dummyNode.next;

Time and Space complexity

As we see, our solution is providing results on the first run. Therefore, we even managed to fulfil the bonus part of the LeetCode problem solution required to solve the problem with one pass on the linked list.

Time Complexity: O(N), where N is the number of nodes in the given list. We need to loop once through all the nodes to get with the fast pointer to the end of the given linked list.

Space Complexity: O(1), since we do not use any auxiliary space and use only constant space for slow and fast pointers.

Time and Space complexity

package com.bigocrazy.leetcode;

import org.junit.Assert;
import org.junit.Test;

import com.bigocrazy.leetcode.Solution;

public class TestCases {

    @Test
    public void testLeetcodeBasicExample1() {

        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

        ListNode result = Solution.removeNthFromEnd(head, 2);

        Assert.assertEquals(1, result.val);
        result = result.next;
        Assert.assertEquals(2, result.val);
        result = result.next;
        Assert.assertEquals(3, result.val);
        result = result.next;
        Assert.assertEquals(5, result.val);
        Assert.assertEquals(null, result.next);
    }

    @Test
    public void testLeetcodeBasicExample2() {

        ListNode head = new ListNode(1);

        ListNode result = Solution.removeNthFromEnd(head, 1);

        Assert.assertEquals(null, result);
    }

    @Test
    public void testLeetcodeBasicExample3() {

        ListNode head = new ListNode(1, new ListNode(2));

        ListNode result = Solution.removeNthFromEnd(head, 1);

        Assert.assertEquals(1, result.val);
        Assert.assertEquals(null, result.next);
    }

}

Additional thought

The problem only asks us to remove the node from the linked list and not delete it. So a good question to ask the interviewer is if it is also required to remove the node from the linked list or completely delete it from memory. Since this problem has not been stated, if the node is not needed somewhere else, it is still better to remove the node from the linked list as asked.

However, if we want to delete the node altogether, then we will free the memory by assigning NULL to the removed node from the linked list before returning the linked list head from the method.

Conclusion

This article has shown how to solve the 19th LeetCode problem Remove Nth Node From End Of The List. We hope that the solution for this problem was easy to clear and easy to understand.

Do you know other ways how to solve this problem? Did you find a mistake in our solution? Or have you found a similar question on other platforms? Let us know in the comment to adjust the description, and your contribution will help others better solve this problem.