LintCode 删除連結清單中倒數第n個節點

給對外連結表1->2->3->4->5->null和 n = 2.

删除倒數第二個節點之後，這個連結清單将變成1->2->3->5->null.

這個題目相當于在“傳回連結清單倒數第n個節點”的基礎上增加功能，通過上一篇文章，我們已經有了尋找倒數第n個節點的方法。這裡我們隻提供周遊一次的方法，周遊2次也是這個道理。

删除節點k的關鍵在于要找到k的前一個節點，其次就是特殊情況的判斷。代碼如下：

<span style="color:#717171;">class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        ListNode *p1, *p2, *pre;
        if ( head == NULL || n <= 0 ) {
            return NULL;
        }
        p1 = head;
        p2 = head;
        for ( int i = 0; i < n-1; i++ ) {
            if ( p1 -> next != NULL ) {
                p1 = p1 -> next;
            } else {
                return NULL;
            }
        }
        while ( p1 -> next != NULL ) {
            p1 = p1 -> next;
            pre = p2;        //關鍵一步：标記倒數第n個節點的前一個節點
            p2 = p2 ->next;
        }
        if ( p2 == head ) {  //關鍵判斷：如果隻有一個節點，倒數第n個就是第一個，删除後連結清單為空
            head = head -> next;
        } else {
        pre ->next = pre -> next -> next;
        }
        return head;
    }
};</span>