LeetCode | Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

首先，dummy node还是要先建起来的，然后分别解决两个子问题：

1. 找到链表中的倒数第n个节点
2. 删除链表中特定节点

对子问题1，O(n)的解法是用两个指针。具体参见 http://www.cnblogs.com/ilovezyg/p/6376314.html

我是找到倒数第(n+1)个节点（由于有dummy node，所以是可行的），因为这样删除目标节点会比较容易些。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head || n <= 0) return head;
        
        ListNode dummy(0); dummy.next = head;
        
        // find the (n+1)-th node from end
        ListNode *main_ptr = &dummy, *ref_ptr = &dummy;
        for (int i = 1; i < n + 1; ++i) {
            ref_ptr = ref_ptr->next;
            if (!ref_ptr) return head;
        }
        while (ref_ptr->next) {
            main_ptr = main_ptr->next;
            ref_ptr = ref_ptr->next;
        }
        
        // delete the n-th node from end
        ListNode *next = main_ptr->next;
        main_ptr->next = main_ptr->next->next;
        delete next;
        return dummy.next;
    }
};