Simple O(N) C++ solution using dummy node


  • 0
    S

    below is my simple solution, just have a question, how do I need to delete dummy node? Or, is there any other ways to avoid extra space?

    ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode* dummy = new ListNode(0);
            dummy->next = head;
            ListNode* slow_ptr = dummy;
            ListNode* fast_ptr = dummy;
            for(int i = 0; i < n; ++i) {
            	fast_ptr = fast_ptr->next;
            }
            while(fast_ptr->next) {
            	slow_ptr = slow_ptr->next;
            	fast_ptr = fast_ptr->next;
            }
            ListNode* to_be_deleted = slow_ptr->next;
            slow_ptr->next = slow_ptr->next->next;
            delete to_be_deleted;
            return dummy->next;
        }

Log in to reply
 

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