问题链接

题目解析

给定链表，将倒数第n个元素删除后返回新的链表。

解题思路

这应该是一道简单题，不知道为什么是Medium。题目中已经给了提示，遍历一次！本题中由于不知道链表有多长，如果想知道的话需要遍历一次，找到倒数第n个元素有需要遍历一次，不符合题意。

使用两个指针cur、pre，其中cur比pre先行n步，当cur到达末尾时，pre所指的下一个元素即是要删除的元素。

时间复杂度：\(O(n)\)。

参考代码

/** * 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 *cur = head, *pre = head;        while(n--) cur = cur->next;        if(cur == NULL) return head->next;        while(cur->next) {            pre = pre->next;            cur = cur->next;        }        pre->next = pre->next->next;        return head;    }};

---

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

---