Simple one pass 4ms C++ implementation


  • 9
    X
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode realHead(0);
            realHead.next = head;
            head = &realHead;
            ListNode *curr = &realHead;
            while (n-- > 0)
                curr = curr->next;
            while (curr->next != nullptr) {
                curr = curr->next;
                head = head->next;
            }
    
            head->next = head->next->next;
            return realHead.next;
        }
    };

  • 0
    C

    memory leak. The deleted one is not released. Also, when n < list length, may wrong.


  • 0
    X

    If you go back to the problem, there is a note saying "Given n will always be valid". As for the memory leak, it depends. If the memory is allocated on the stack or on the heap but using smart pointer, then we do not need to worry about the deallocation.

    Below is a version based on the assumptions that n could be invalid and we return the original list without any changes for an invalid n. The ListNode memory is allocated using the keyword 'new' and never get released elsewhere in the program.

    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
    		if (n <= 0 || head == nullptr)
    			return head;
    		
            ListNode realHead(0);
            realHead.next = head;
            head = &realHead;
            ListNode *curr = &realHead;
            while (curr != nullptr && n-- > 0)
                curr = curr->next;
    			
    		if (curr == nullptr) // here check if n is larger than the length of the list
    			return realHead.next; // we return the original list without any changes
    			
            while (curr->next != nullptr) {
                curr = curr->next;
                head = head->next;
            }
    		
    		curr = head->next;
            head->next = curr->next;
    		
    		if (curr != nullptr) // release the memory of the node
    			delete curr;
    		
            return realHead.next;
        }
    };
    

Log in to reply
 

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