Remove Nth Node from End of Linked List

Question

I am solving the well known problem Remove Nth Node From End of List:

Given a linked list, remove the n-th node from the end of list and return its head. Assume that n is between 0 and the length of the list.

Example:

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

This is my solution:

public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || n == 0)
            return head;
        ListNode slow = head;
        ListNode fast = head;
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode pre = newHead;
        int steps = 1;
        while(steps <= n){
            fast = fast.next;
            steps++;
        }
        if(fast == null)
            return head.next;
        while(fast.next != null){
            pre = pre.next;
            slow = slow.next;
            fast = fast.next;
        }
        if(slow.next != null)
            slow.next = slow.next.next;
        else // slow.next = null, i.e. I have to remove the last node
            pre.next = null;
        return head;
    }

and this is the definition of ListNode class:

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

What I don't like in my code is that I handle every edge case separately. Is there more sophisticated way to deal with the edge cases? Also the following code fragment:

       while(steps <= n){
            fast = fast.next;
            steps++;
        }

Is this the right condition for traversing the list? This definitely works, but is it better to rewrite my code in terms of

      while(steps < n){
            fast = fast.next;
            steps++;
      }

Answer 1

Bug

I cannot remove an element from a one-element list. You could easily fix this by adding this after your initial check:

if(head.next == null && n == 0) {
    // return empty list
}

ListNode and the need for a List

The questions starts with Given a linked list. But you don't really have a linked list. You have a node class, but that's it, and that's really not enough. Right now, I would have to take your word that it does what it is supposed to, because there is no way of knowing if it actually does (well, except reading the code :) ).

Creating something like a list, I would have to do this:

    ListNode n = new ListNode(1);
    n.next = new ListNode(2);
    n.next.next = new ListNode(2);

And if I want to write unit tests as @Pimgd suggested (or even just check with a simple example in a main method), I would need to add a whole lot of code. I would suggest that you at least add methods to add elements, to traverse through the list, to check if one list is equal to another, and a toString method.

This would make debugging and testing your code a lot easier, and some of those methods would also help you implement the removeNthFromEnd method.

Handling Exceptions

Don't just accept any input. You are already checking if(head == null || n < 0), which is good, but it would be best to throw an IllegalArgumentException.

If the user tries to remove an element that doesn't exist, don't just let them, throw an IndexOutOfBoundsException instead.

while loop

    while(steps <= n){
        fast = fast.next;
        steps++;
    }

Your first while loop looks better as a for loop:

for (int steps = 1; steps <= n; steps++) {
    fast = fast.next;
}

As to your question, it doesn't really matter if you start at 1 or 0. I would start at 0, but it's just a personal preference.

Naming and Comments

I just want to emphasize what @Pimgd and @shivsky said. You really need better names than fast and slow, and if the program isn't a lot clearer then, also comments (see this code for an example; you don't need that many comments, but something like set p1 and p2 apart by n-1 nodes initially etc is really helpful).

You should also have a method comment. It should state if the list is changed or if a new (changed) list is returned (or what else is returned if not a new list), what arguments are acceptable, etc.

You should also make clear how your indices work. Does nth from last mean that I remove the last node with removeNthFromEnd(0) or removeNthFromEnd(1)?

Misc

• declare your function as static to express how it works (it doesn't belong to a specific ListNode and changes that).
• use curly brackets even for one-line statements. If you really don't want to, put the line on the same line as the if statement. Otherwise it's easy to introduce bugs.

Answer 2

Bug: n < 0 leads to you removing the last node.

Your solution should have comments: I have NO idea how it works. And that's after reading it a couple times. If this was production code, I'd have wrapped it with unit-tests, thrown the implementation away and rewrote it.