題目
給定一個鏈表怠堪，刪除鏈表的倒數(shù)第 n 個節(jié)點埠通，并且返回鏈表的頭結(jié)點维咸。

示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數(shù)第二個節(jié)點后涣澡，鏈表變?yōu)?1->2->3->5.

說明：
給定的 n 保證是有效的跛锌。

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

思路
1.構(gòu)造雙指針
首先我們將添加一個啞結(jié)點作為輔助弃秆，該結(jié)點位于列表頭部。啞結(jié)點用來簡化某些極端情況髓帽，例如列表中只含有一個結(jié)點菠赚，或需要刪除列表的頭部。在第一次遍歷中郑藏，我們找出列表的長度 LL衡查。然后設(shè)置一個指向啞結(jié)點的指針，并移動它遍歷列表必盖，直至它到達第 (L - n)(L?n) 個結(jié)點那里拌牲。我們把第 (L - n)(L?n) 個結(jié)點的 next 指針重新鏈接至第 (L - n + 2)(L?n+2) 個結(jié)點，完成這個算法歌粥。

image.png

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* copyList = head;
        
        
        int lengthOfList = 0;
        while (copyList != NULL)
        {
            lengthOfList++;
            copyList = copyList->next;
        }
        lengthOfList -= n;
        ListNode* result = copyList;
        while (lengthOfList > 0)
        {
            lengthOfList--;
            copyList = copyList->next;
        }
        copyList->next = copyList->next->next;
        return result->next;
    }

2.構(gòu)造雙指針（兩個指針間隔n）
上述算法可以優(yōu)化為只使用一次遍歷们拙。我們可以使用兩個指針而不是一個指針。第一個指針從列表的開頭向前移動 n+1步阁吝，而第二個指針將從列表的開頭出發(fā)⊙馄牛現(xiàn)在，這兩個指針被 n 個結(jié)點分開。我們通過同時移動兩個指針向前來保持這個恒定的間隔装盯，直到第一個指針到達最后一個結(jié)點坷虑。此時第二個指針將指向從最后一個結(jié)點數(shù)起的第 n個結(jié)點。我們重新鏈接第二個指針所引用的結(jié)點的 next 指針指向該結(jié)點的下下個結(jié)點埂奈。

image.png

    ListNode* removeNthFromEnd2(ListNode* head, int n)
    {
        ListNode* preNode = head;
        ListNode* curNode = head;

        while (n-- != 0) curNode = curNode->next;
        if (curNode == NULL) return preNode;
        while (curNode->next != NULL)
        {
            preNode = preNode->next;
            curNode = curNode->next;
        }
        preNode->next = preNode->next->next;
        return head;
    }

/**插入指針**/
    void inserNode(ListNode* p, int i)
    {
        ListNode* node = new ListNode(1);
        node->val = i;
        node->next = p->next;
        p->next = node;
    }

int main(int argc, char* argv[])
{
    int a[] = { 1,2,3,4,5 };
    ListNode* test = new  ListNode(1);
    ListNode* result;
    for (int i : a)
    {
        Solution().inserNode(test, i);
    }
    result = Solution().removeNthFromEnd(test, 2);
    system("pause");
    return 0;
}