A recursive solution


  • 1
    L

    The code doesn't use stack, but the process which executes the code uses stack. So code is clean while space is still O(n).

     class Solution {
        public:
            ListNode *removeNthFromEnd(ListNode *head, int n) {
        		if (n <= 0 || head == nullptr)
        			return head;
        		return doRemoveNthFromEnd(head, n);
            }
        private:
            ListNode *doRemoveNthFromEnd(ListNode *head, int & n) const {
        		if (head == nullptr) {
        			n = -n;
        			return head;
        		}
        
        		ListNode * next = doRemoveNthFromEnd(head->next, n);
        		++n;
        		if (n != 0) {
        			head->next = next;
        			return head;
        		} else {
        			return next;
        		}
            }
        };

Log in to reply
 

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