题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

样例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

算法1

(两遍遍历) $O(n)$

先遍历一遍链表可以得到链表的长度len，然后再遍历第二遍找到第len-n个结点的前驱结点，然后删除第len-n个结点。其中有个特殊情况，如果len == n，那么他的前驱结点找不到，所有要特殊处理，这里直接head = head->next就可以了。

时间复杂度

$O(n)$

参考文献

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *pre = head;
        int len = 0;
        while(pre){
            len++;
            pre = pre->next;
        }
        ListNode * pre1 = head;
        if(len==n){
            head = head->next;
            return head;
        }
        for(pre1 = head;pre1!=NULL,len>n+1;len--,pre1 = pre1->next){
        }
        ListNode *pre2 = pre1->next;
        pre1->next = pre2->next;
        delete pre2;
        return head;
    }
};