Leetcode --- Remove Nth Node From End of List
===

## Two Pass

先求總長度l，再用l-n就可以知道正數來說要刪第幾個node

時間複雜度: ==O(N)==
空間複雜度: ==O(1)==

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int l= 0;
        auto pt= head;
        while(pt)
        {
            ++l;
            pt= pt->next;
        }
        pt= head;
        for(int i=0 ;i< l-n- 1; ++i)
            pt= pt->next;        
        if(l == n) return head->next;
        auto kill= pt->next;
        pt->next= pt->next->next;
        delete kill;
        return head;

    }
};

## One Pass

以下面圖片為例，我想要在頭的地方走l-n步到要刪除node的前一個node，這樣就可以解了，l為整串List的長度，因此我可以使用一個pt1先走n步，再開始走另一個pt2，這樣pt1走到底的時候，pt2會剛好走l-n步

時間複雜度: ==O(N)==
空間複雜度: ==O(1)==

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto fast= head, slow= head;
        for(int i= 0; i< n; ++i)
            fast= fast->next;
        if(!fast) return head->next;
        while(fast->next)
        {
            fast= fast->next;
            slow= slow->next;
        }
        auto tmp= slow->next;
        slow->next= slow->next->next;
        delete tmp;

        return head;
    }
};