3ms C++ solution beats 100%


  • 1
    H

    Code first, followed by explaination.

    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int& n) {
            auto node = new ListNode(0);
            node->next = head;
            removeNode(node, n);
            return node->next;
        }
        
        void removeNode(ListNode* head, int& n){
            if(!head) return;
            removeNode(head->next, n);
            n--;
            if(n == -1) {
                head->next = head->next->next; 
            }
            return;
        }
    };
    
    • The intuitive way :
      1. count the number of node ( N ) .
      2. get the (N-n)th node from beginning.

    This approach will go through the list for exact 2 loops.


    • My version of implementation is to do the counting and deleting in "basically" 1 loop.

    • The trick is int& n . When recursively going through the list, the same n will pass down the recursion because & sign means passing the reference down.

    • When reach the end of the list. n start to decrement. When n hits -1, that means we are at (n+1)th node from the end, then we can do the deletion.


    This solution was definitely inspired by someone else on some other problem. But I can't seems to find that problem or person. Thanks to whoever inspired me.


  • 0
    Z

    my thought is same as you.Here is my code:

    class Solution {
    public:
     ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode *p; int len = 0; p = head;
            /*get the length*/
            while(p != NULL){ p = p -> next;++len;}
            
            n = len - n; //index from 0
            if(n == 0){ head = head -> next; return head;}
            
            /*delete the nth node*/
            ListNode *q; p = head;
            for(int i = 0; i < n-1; ++i){ p = p -> next;}
            q = p -> next; p -> next = q -> next;
            delete q;
            return head;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.