19. Remove Nth Node From End of List

19. Remove Nth Node From End of List:题目链接

方法1

基本思想： 指针p，q指向头节点，将q往后移动k位，当q不为空时，p，q同时往后移，当q为空时，此时p在倒数第k位上

假设k = 2
        dummyHead -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
初始：     p、q
q移k位:     p         	  q
只要q不空，p、q后移    p          q
                          p         q
                                p        q
此时p就在倒数第k位                    p          q

AC代码：

// 时间复杂度O(n)  空间O(1)
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (head == NULL || n <= 0) {
        return head;
    }
    struct ListNode * dummyHead = (struct ListNode *) malloc (sizeof(struct ListNode));
    dummyHead->next = head;

    int i = 0;
    struct ListNode * p = dummyHead, *q = dummyHead, *pre = dummyHead;
    // 找到q的位置
    while (i < n && q) {
        q = q->next;
        i++;
    }
    // q不空p、q同时后移 pre是p的前驱
    while (q != NULL) {
        pre = p;
        p = p->next;
        q = q->next;
    }

    pre->next = p->next;
    free(p);
    p = NULL;
    return dummyHead->next;
}

pS: 源代码链接