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

描述
给定一个链表，删除链表的倒数第n个节点并返回链表的头指针。例如，给出的链表为: 1→2→3→4→5, n= 2。删除了链表的倒数第n个节点之后,链表变为1→2→3→5.
备注：题目保证n一定是有效的
请给出请给出时间复杂度为O(n)的算法

示例1
输入：{1,2},2
返回值：{2}

方法一：快慢指针
核心思想：
利用快慢双指针完成删除链表倒数第n个节点。假设链表的节点数为n，想要删除到数第k个节点(k<=n)，则当快指针指向第k+1个节点时，此时慢指向第一个节点。快慢指针的差距为k个节点，你那么当快指针指向最后一个节点时(第n个节点)，此时慢指针指向第n-k个节点。那么此时倒数第k个节点为慢指针所指的后继节点。

图解：
图片说明

核心代码：

ListNode* removeNthFromEnd(ListNode* head, int n) {
   if(head == NULL){
        return head;
    }
    ListNode* dummy = new ListNode(0);     //创建一个空节点作为头结点
    dummy->next = head;
    head = dummy;                  //head指针指向真正的头结点
    ListNode* slow = head;
    ListNode* fast = head;
    for(int i = 0; i <n; i++){     //先让快指针后移n个节点
        fast = fast ->next;
    }
    while(fast->next != NULL){     //快慢指针同时移动，直到快指针移动到链表最后一个节点，此时慢指针刚好指向倒数第n个节点的前驱节点
        fast = fast->next;
        slow = slow->next;
    }

    //删除慢指针所指节点的后继节点(后继节点刚好为倒数第n个节点)
    ListNode* temp = slow->next;
    slow ->next = slow->next->next;
    delete temp;
    return head->next;
}

复杂度分析：
代码循环遍历链表，循环次数为链表的长度，因此该方法的时间复杂度为O(N)。由于没有采用额外的空间，因此空间复杂度为O(1)
时间复杂度O(n)
空间复杂度O(1)

方法二：直接节点倒数第n个节点的位置
核心思想：
从头遍历链表计算出链表的长度L，则倒数第n个节点即为顺着的第L-n+1个节点，因此需要删除该节点。

核心代码：

int getLength(ListNode* head) {      //计算链表长度
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
   if(head == NULL){
        return head;
    }
    ListNode* dummy = new ListNode(0);     //创建一个空节点作为头结点
    dummy->next = head;

    ListNode* cur = dummy;
    int i,length = getLength(head);      //计算链表长度
    for (i = 1; i < length - n + 1; i++) {       //找到倒数第n个节点的前驱节点
        cur = cur->next;
    }
        //删除慢指针所指节点的后继节点(后继节点刚好为倒数第n个节点)
    ListNode* temp = cur->next;
    cur->next = cur->next->next;
    delete temp;
    return dummy->next;
}