One-pass recursion C solution


  • 0
    D

    The code needs one-pass only. While the drawback of this recursion solution is that it's cumulatively costing stack space thus not suitable for very long (e.g., length = tens of thousands) linked list. Actually I like the 2-pointer solution which costs O(n) time & O(1) space.

    struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
        if(n==0) return head;
        
        static int nodes_amount = 0;
        nodes_amount++;
        if (head->next != NULL) removeNthFromEnd(head->next, n);
        static int pos_from_tail = 0;
        pos_from_tail ++;
        
        // remove the node
        if(pos_from_tail == n && n == nodes_amount) head = head->next; // current position is at original head
        else if(pos_from_tail == n + 1)  head->next = (head->next)->next; // current position is at one node ahead the target node
        
        if(pos_from_tail == nodes_amount) pos_from_tail = nodes_amount = 0; // reset for next call
        return head;
    }
    

  • 0
    D

    Same thing (With a nested function):

    struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
        struct ListNode dummy = {0, head};
        struct ListNode* node_nPlus1 = NULL;
        static int pos_from_tail = 0;
        void foo(struct ListNode* h){
            if (h->next != NULL) foo(h->next);
            if (++pos_from_tail == n+1) node_nPlus1 = h;
        }
        foo(&dummy); // pos_from_tail will be n+1
        
        // remove the node
        node_nPlus1->next = (node_nPlus1->next)->next; // remove the node
        pos_from_tail = 0; // reset for next case
        return dummy.next;
    }
    

    Runtime is randomly from 3ms (beats 96%) to 9ms (beats 1%). Weird...


Log in to reply
 

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