5
\$\begingroup\$

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++;
      }
\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Thanks for the comments. However, I don't agree that there is a bug. I tested my solution here: oj.leetcode.com/problems/remove-nth-node-from-end-of-list and initially I got wrong answer for the case L = {1} and n = 1, i.e. for one element list as you said. However, I fixed it and now it works correctly (at least my solution was accepted from the system) \$\endgroup\$ – user3371223 Sep 18 '14 at 18:32
  • \$\begingroup\$ @user3371223 my bad, I used n = 0. And as the structure was given to you, I guess most of my other comments don't really apply either. \$\endgroup\$ – tim Sep 18 '14 at 18:47
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Well-named sub-functions and variables can do the trick just as well as comments (I'd actually prefer that to comments!) but I agree that seeing bizarre variable names like fast and slow is the type of thing that I'd hate to see my team check into in my own project's production code. \$\endgroup\$ – shivsky Sep 18 '14 at 13:46
  • \$\begingroup\$ Thanks. I added comments. I hope now it is more clear what I am trying to do. Also I assumed that the values of n are between 0 and the length of the list. \$\endgroup\$ – user3371223 Sep 18 '14 at 15:22
  • \$\begingroup\$ Comments would have made it better, but I didn't find this function too hard to understand without them. There are only two obvious strategies: recursion or iteration. As soon as I saw that it uses iteration, and that there were two variables named fast and slow, I basically knew the outline of the plot. \$\endgroup\$ – 200_success Sep 18 '14 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.