My short C++ solution


  • 69
    T
    class Solution
    {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n)
        {
            ListNode** t1 = &head, *t2 = head;
            for(int i = 1; i < n; ++i)
            {
                t2 = t2->next;
            }
            while(t2->next != NULL)
            {
                t1 = &((*t1)->next);
                t2 = t2->next;
            }
            *t1 = (*t1)->next;
            return head;
        }
    };

  • -21
    A

    what a clever and elegant code it is !!!


  • 0
    X

    Really smart!


  • 0
    R

    great solution!


  • 4
    H

    I see a memory leak...


  • 0
    X

    could anyone give some explanation? thx


  • 0
    P

    unbelivable!!!!!!!


  • 3
    L

    I wonder why **t1=&head, instead of *t1=head


  • 0
    L

    you didn't delete the node, it is still in the heap


  • 0
    L

    basically you need a pointer (call it p1) iterate through the first n terms in the list(try to think it as an offset), then you keep iterate the p1, when it reach to the end, your second pointer call it p2, will be at the exact nth position from the end.


  • 9
    X

    **t1保存的是当前指针next的内存地址,到时候删除就方便了,给你个详细解释:http://blogread.cn/it/article/6243?f=wb


  • 0
    J

    what if the list has only one node and n == 1?
    then
    while(t2->next != NULL)
    will cause a runtime error.


  • 0
    T

    See the problem note


  • 6
    F

    Your solution is very smart!!! But the double pointer let me difficult to understand. So I rewrite you solution.
    Thank for your solution.

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* ans;
        ListNode* slow = head;   //t1
        ListNode* fast = head;    //t2
        
        for(int i=0;i<n;++i)
        {
            fast = fast->next;
        }
        
        if(fast == NULL) 
        {
            ans = head->next;
            delete head;
            return ans;
        }
        
        while(fast->next != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        delete slow->next;
        slow->next = slow->next->next;
        
        return head;
    }
    

  • 3
    T

    Thanks for sharing.
    Here is a recursive solution.

    code:

    int countAndRemove(struct ListNode *node, int n){
         
        //Once the stack frame reaches the tail, counting starts.
        if(!node->next) return n-1;
                
        int NumOfNodesLeft = countAndRemove(node->next, n);
        
        //If there are exactly n nodes in the rest of the list, delete next node.
        if(NumOfNodesLeft  == 0)  node->next = (node->next)->next;
        
        //Count decremented.         
        return NumOfNodesLeft - 1;
    }
                
     struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
        return (countAndRemove(head, n) == 0)? head->next : head;
      }
    

    The idea is based on how function call, namely pushing and popping stack frames, works.

    i) Push as many stack frames as the size of linked list. so n is passed to the end (top frame).
    ii) As the last frame pops off, counting begins. 
    

    Suppose there S nodes in the linked list.

    The stack frames would be like the following:

    ===================================================

    Sth stack: 1st node ( counting from the back ) n = n, NumOfNodesLeft = n, return n - 1.

    ===================================================

    (S-1)th stack: 2nd node ( from the back ), n = n, NumOfNodesLeft = n - 1, return n - 2.

    ===================================================

    :

    ===================================================

    (S-n-1)th stack: 2nd node ( from the back ), n = n, NumOfNodesLeft = 0, return -1.

    Only this frame does the deletion.

    ===================================================

    :

    ===================================================

    Second stack: (S-1)Th node ( counting from the back ), NumOfNodesLeft = n - (S -1), return n - (S-1) - 1.

    ===================================================

    First stack: Sth node from the back / 1st node in the list, NumOfNodesLeft = n - S, return n - S - 1.

    ===================================================


  • 0
    J

    memory leak!


  • 0
    F

    Thank you for your advice


  • 0
    V

    t1 = &((*t1)->next);
    *t1 = (*t1)->next;
    can u explain me what each of these two lines are doing?


  • 0

    I want to know why does slow->next = slow->next->next; work even we have already delete slow->next;?


  • 0

    Hi, tim14. Your code is good. But it seems that you need a good format setting to help people read it.


Log in to reply
 

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