题解 | #删除链表的倒数第n个节点#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    /**算法思路如下：快指针先向后遍历n个元素，然后慢指针从头开始和快指针一起遍历，当快指针到达末尾的时候，慢指针恰好指向倒数第n个元素。另外由于题目保证n有效，因此不需要考虑链表不足n的情况出现*/
    int count=1;
    struct ListNode* p=head;
    while(count++<n){
        p=p->next;
    }//找到第n个元素
    struct ListNode* q=head;
    p=p->next;
    while(p!=NULL){
        p=p->next;
        q=q->next;
    }
    struct ListNode* t=head;
    if(t==q) return head->next;
    while(t->next!=q){
        t=t->next;
    }
    t->next=q->next;
    free(p);
    return head;
}

解题思路如注释部分所示，这里需要注意的一个点是关于脚标和位序之间的不一致，因此p本身要先向后移动一位才能和q一起同步，另外，程序之所以需要三个指针而不是直接使用两个指针是为了头节点被删除的一致性。（当然双指针也是可以的，对于头结点的删除单独处理即可）