1
\$\begingroup\$

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

For example,

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.

ListNode *removeNthFromEnd(ListNode *head, int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (head == NULL) {
      return NULL;
    }

    ListNode *pre, *cur;
    pre = cur = head;
    for (int i = 0; i < n; ++i) {
      pre = pre->next;
    }

    while (pre != NULL && pre->next != NULL) {
      cur = cur->next;
      pre = pre->next;
    }

  //mistake
  //if (cur == head) {
  // I use the above line to check if it's the first node to be deleted, 
  // there is a problem for this case: list: 1->2, n : 1
    if (pre == NULL) {
      ListNode *newHead = head->next;
      delete head;
      return newHead;
    }
    else {
      ListNode *tmp = cur->next;
      cur->next = tmp->next;
      delete tmp;
      return head;
    }        
}
\$\endgroup\$

closed as off-topic by Mathieu Guindon, Jamal, Malachi, Kinjal, palacsint Nov 17 '13 at 8:10

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ This question appears to be off-topic because it is not clear whether it's asking for code to be written; also the code being embedded in a block quote makes it looks like it's not the OP's code. \$\endgroup\$ – Mathieu Guindon Nov 17 '13 at 3:16
  • 1
    \$\begingroup\$ @retailcoder: Based on the tag, I assume this was straight from the interviewer. But I cannot tell for sure, so I agree with your close reason. \$\endgroup\$ – Jamal Nov 17 '13 at 3:37
1
\$\begingroup\$

Your function fails if n is 0 or greater than the list size.

Also, I prefer to see one variable defined per-line:

ListNode *pre = head;
ListNode *cur = head;

And the opening brace belongs in column 0 (I guess you don't agree, but there are - or were anyway - tools that rely on this).

An alternative implementation might use a function to find the number of entries in the list and another to return a specified entry (size - n - 1, in this case). Then once you've checked that 0 < n <= size, the main function is simple - but no better than yours :-)

BTW, delete is C++, not C

\$\endgroup\$
  • 1
    \$\begingroup\$ If there are tools that rely on the code being formatted in non-K&R-style, then it's not the code that is wrong, it is the tools. Both The C Programming Language and The C++ Programming Language books use this style. Admittedly not for functions, but it's still perfectly valid C and C++. Which tools rely on the opening brace being in column 0? \$\endgroup\$ – Lstor Jun 20 '13 at 0:53

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