Remove nth node from last position in linked list

Question

Description:

Given a linked list, remove the n^th node from the end of list and return its head.

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid. Try to do this in one pass.

Code:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int total = 0;
        ListNode current = head;
        while (current != null) {
            total++;
            current = current.next;
        }
        // current must be null here

        // 1 based index
        int indexToRemove = total - n + 1;
        if (indexToRemove < 0) {
            return null;
        }
        if (1 == total && n == 1) {
            return null;
        }
        if (indexToRemove == 1) {
            return head.next;
        }

        current = head;
        ListNode prev = null;
        for (int i = 0; i < indexToRemove - 1; i++) {
            prev = current;
            current = current.next;
        }
        // i > indexToRemove

        if (current == null) { // last
            prev.next = null;
        }
        else {
            prev.next = current.next;   
        }
        return head;
    }
}

Questions:

I managed to run the code and pass all the tests but I still feel confused while dealing with off-by-one errors and NullPointerException. The question felt quite easy at first but implementation took a lot of time because of above two errors and correcting them, it was like I was shooting in the dark.

I still feel I have written a lot of extra code which could have been avoided.

What mental model or basic rules I can learn to visualise or understand program states and avoid such errors?

Answer 1

You failed to solve the "try to do this in one pass" part, as you iterate through the list once to find the total size and a second time to find the nth element from the start.

The algorithmic idea is, to use two pointers into the list:

• Initialize poiner1 to head, advance n times (if n is the distance from the tail you seek)
• Then, initialize pointer2 to head, advance both pointers, until pointer1 is null, i.e. reached the end of the list.
• Now, pointer2 should point to the end-nth element

Removal as usual.

Answer 2

I will structure my answer in the following way:

• General (java) nitpicks
• Direct remarks about your implementation
• Improvements
• How it could look like

General nitpicks:

• First thing you always should do is check your arguments for any invalid input. What if head==null? What if n<0? Make the assumptions on your arguments explicit and get that out of the way immediately, it will make it easier to think about the rest, because these edge cases are eliminated.

• Make your method static if there are no instance (non-static) fields you are using.

• There are several things going on here that could be extracted in dedicated methods, which would improve readability and make it possible for reuse. Candidates: getting the length of linked list and removing some element in linked list by index.

• Never reuse any variables, it costs nothing to create a new one and it makes it clearer. Even if the two variables have the same purpose, like walking over a linked list. It just adds mental load, because potentially some state could be shared between them if you forget to initialize it properly the second time.

Implementation remarks:

I will assume that n being valid means 1 < n <= total+1 and that head!=null. If head==null or invalid n everything breaks. I will give my remarks by going over the code piece by piece

• Find length of linked list.
• Use the previous length to flip n to get an index, still with 1-indexing, from the front.

• you create three branches and return early. The second is redundant, because n==1&&total==1 => indexToRemove==1 && head!=null && head.next==null.

• Isn't indexToRemove 1-indexed? Doesn't that mean it is at least 1? Are you protecting against invalid n here? You only protect against n>total+1.

• you walk over the list till you hit the node that should be removed, remembering the previous node because you have to change the pointer there.

• As long as n>=0 you are guaranteed that you will not have a NPE with current.next, because of the first loop. This is a not very clear to see though, because you count the length in the first loop and then do some arithmetic operations on this length and some argument and then you try to loop over the list again with the outcome. Some better ways are make it clear when calculating indexToReturn by adding a max(.., total+1) or use total to loop the second time and break when you are at the right node.
• After the second loop i>indexToRemove -1 so since you increment by 1 we have i==indexToRemove. What you wrote in the comment is wrong. This makes the first if block unnecessary and dead code.
• Now you are at the node you want to delete, so you set the pointer of the previous node to null and you are done.

Improvements:

All the things I said under general nitpicks.

Change the unnatural 1-indexing into the super common 0-indexing. This will improve readability and decrease the chance of off-by-one errors.

How I would do it:

I choose to check for n that is too big in both methods because I like self-contained methods. In principle I could remove it from removeItemFromEnd and remove the call to size to save time. It will not help the time complexity and it makes the methods more coupled, so here I pick structure over speed.

class Solution {
    public int size(ListNode head) {
        int total = 0;
        ListNode current = head;
        while (current != null) {
            total++;
        }
        return total;
    }

    public removeItem(ListNode head, int index) {
        if (index < 0) {
          throw new IndexOutOfBoundsException("Index " + index + " is too small.");
        }
        if (head == null) {
            return null;
        }

        if (index == 0){
            return head.next;
        }


        ListNode current = head;
        ListNode prev = null;
        for (int i = 0; i < index && current != null; i++) {
            prev = current;
            current = current.next;
        }

        if (current == null) {
           throw new IndexOutOfBoundsException("Index " + index + " is too big.");
        }
        prev.next = current.next;
        return head;
    }

    public ListNode removeItemFromEnd(ListNode head, int n) {
        if (head == null) {
           return null;
        }

        if (n<1) {
           throw new IndexOutOfBoundsException("Index " + n + " is too small.");
        }



        int size = size(head);
        if (n > size){
           throw new IndexOutOfBoundsException("Index " + n " is too big.");
        }

        return removeItem(head, size - n); // size - n is zero indexed
    }
}

Answer 3

The part below seems unnecessary and incorrect to me:

    if (indexToRemove < 0) {
        return null;
    }

If I get it correctly, you say n is always valid. Based on the example, I understand it means n is not less than 1 and not greater than the list's length. Hence the indexToRemove can't be negative and the whole if() is void.

Anyway, even if you consider invalid n, you can't remove a non-existing item, but the head of the list stays untouched in such case, so I'd expect return head; here. However, then the condition should be indexToRemove <= 0.

Also the next conditional branch is unnecessary:

    if (1 == total && n == 1) {
        return null;
    }

because that case is perfectly handled by the statement following it:

    if (indexToRemove == 1) {
        return head.next;
    }

The comment you left after the last loop seems misleading:

    for (int i = 0; i < indexToRemove - 1; i++) {
        prev = current;
        current = current.next;
    }
    // i > indexToRemove

The loop loops as long as the condition i < indexToRemove - 1 is satisfied.
As i grows by one on each iteration, the condition gets broken when i becomes equal indexToRemove - 1, hence it is less than indexToRemove, opposite to what the comment says!

Finally, this part is also useless:

    if (current == null) { // last
        prev.next = null;
    }
    else { ... }

If n == 1 you want to remove the last item from the list.
Actually, indexToRemove is set to total - n + 1 which results in total, i.e. an index of the last item.

However, the loop's invariant is:

pre: current is a (i+1)-st item
post: current is a (i+2)-nd item

(Verify: on entry, i == 0 and current == head.)

So when the loop terminates at i = indexToRemove - 1 after i++, the last value of i processed was indexToRemove - 2, and current was set to the item at position i+2, i.e. indexToRemove. As a result it can't be null!

All you need to do after the loop is:

    prev.next = current.next;   
    return head;

(with current.next being null iff n==1).