An O(n) time, O(1) space solution without dummy head inspired by Linus Torvalds


  • 4
    U

    It is a traditional two-pointer solution, but without the dummy head to handle edge cases.
    The idea of using the two-star pointer (ListNode **) is inspired by Linus Torvalds (for reference: two-star-programming).

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head;
        for (int i = 0; i < n; i++) fast = fast->next;
        ListNode **prev = &head;
        while (fast) {
            prev = &(*prev)->next;
            fast = fast->next;
        }
        ListNode *current = *prev;
        *prev = current->next;
        delete current;
        return head;
    }
    

  • 0
    V

    Thanks for the link.


Log in to reply
 

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