Remove Nth Node from End of Linked List

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++;
      }

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



• 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.

StackExchange Code Review Q#63247, answer score: 5