4ms C++ solution, cannot be shorter


  • -1
    A

    A tricky situation is that the n-th node from end is just the head. In order to avoid checking this situation separately, I create a dummy node. The code can then be cleare and concise.

    ListNode* removeNthFromEnd2(ListNode* head, int n) { 
    	ListNode *dummy = new ListNode(-1), *slow = head, *fast = head, *preSlow = dummy;
    	dummy->next = head;
    
    	while(--n) fast = fast->next;
    	while(fast->next) {
    		preSlow = slow;
    		slow = slow->next;
    		fast = fast->next;
    	}
    
    	preSlow->next = slow->next;
    	return dummy->next;
    }

  • 0

    "cannot be shorter", lol. "avoid checking [...] The code can then be cleare and concise", lol.

    ListNode* removeNthFromEnd(ListNode* head, int n) { 
        ListNode *slow = head, *fast = head;
        while(n--) fast = fast->next;
        if (!fast) return head->next;
        while(fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
    

    I count 9 lines instead of 10 lines, and 244 bytes instead of 307 bytes. And it is with checking.

    Although the top-voted C++ answer, without the fluff, is even shorter:

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode **slow = &head, *fast = head;
        while (--n) fast = fast->next;
        while(fast->next) {
            slow = &((*slow)->next);
            fast = fast->next;
        }
        *slow = (*slow)->next;
        return head;
    }
    

  • 0
    H

    shouldn't dummy and the deleted node be freed?


Log in to reply
 

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