From wrong to AC C++ implementation


  • 0

    Here is my first C++ implementation but with some bugs.

    As it can not deal with the cases that the node we want to delete is the head node.

    Here is the c++ implementation

    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode *slow=head, *fast=head;
            for(int i=0; i<n; i++) fast=fast->next;
            while(fast){
                slow=slow->next;
                fast=fast->next;
            }
            slow->next=slow->next->next;
            return head;
        }
    };
    

    To avoid the RE caused by deletion of the head node.

    We can re-implement it like this:

    The key is to keep the fast pointer (n+1) step ahead slow pointer.

    Here is the AC implementation

    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode *dummy=new ListNode(-1);
            dummy->next=head;
            ListNode *slow=dummy, *fast=dummy;
            for(int i=0; i<=n; i++) fast=fast->next;
            while(fast){
                slow=slow->next;
                fast=fast->next;
            }
            slow->next=slow->next->next;
            return dummy->next;
        }
    };

  • 0
    L

    what if n=0? It looks like the test doesn't contain this case though. However this doesn't work for n=0 case.


  • 0
    Z

    this is a very good idea, but i think u should remember dummy->next and delete dummy before return to avoid memory leak.


  • 0
    Z

    i think n can not be 0 according to the question


Log in to reply
 

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