0019-删除链表的倒数第N个节点

删除链表的倒数第N个节点

方案一

---

我们需要用两个指针来帮助我们解题，pre和cur指针。首先cur指针先向前走N步，如果此时cur指向空，说明N为链表的长度，则需要移除的为首元素，那么此时我们返回head->next即可，如果cur存在，我们再继续往下走，此时pre指针也跟着走，直到cur为最后一个元素时停止，此时pre指向要移除元素的前一个元素，我们再修改指针跳过需要移除的元素即可

借助单链表实现

C-源代码

---

#include <stdlib.h>

#include "LinkList.h"

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next = head;
    
    struct ListNode *fast = dummy;
    struct ListNode *slow = dummy;
    
    for (int i = 1; i <= n + 1; i++) {
        fast = fast->next;
    }
    
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    struct ListNode *p = slow->next;
    slow->next = p->next;
    free(p);
    
    return dummy->next;
}

void test_0019(void) {
    int arr1[5] ={ 5, 4, 3, 2, 1 };
    struct ListNode *l1 = createNode(arr1, sizeof(arr1) / sizeof(arr1[0]));
    int n = 2;
    
    printNode(l1);
    
    struct ListNode *ret = removeNthFromEnd(l1, n);
    printNode(ret);
}

参考Grandyang