[题目] Given a linked list, remove the nth node from the end of list and return its head. For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: Given n will always be valid. Try to do this in one pass.
[中文翻译] 给定一个链表，删除倒数第n个节点并返回新链表的头。 例如，
给定链表：1->2->3->4->5，以及n = 2。 删除倒数第二个节点后，链表就变成了1->2->3->5。
注意： 给定的n始终是合法的。 尽量只遍历一遍链表。
[解题思路] 朴素的想法，先遍历一遍链表，确定链表有多少节点，然后根据n确定要删除的节点前一个节点的位置，再遍历一遍链表找到该节点，然后删除后继节点。
一次遍历的方法，设定p为head，q与p间隔n-1个节点，p与q同时向后移，直到q后继节点为NULL，此时p即为要删除节点的前一个节点。严格地讲，这种方法和遍历两遍的方法时间复杂度一样，因为p、q同时在遍历，相当于遍历了两遍。不过这两种方法思路不太一样。
给出的代码里，在删除节点前，严格地讲应该要释放空间，但由于不知道节点是new出来的还是malloc出来的，所以就不释放了。
[C++代码] Solution 1，遍历两次链表
class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { int count = 0; ListNode* tmp = head; while (NULL != tmp) { count++; tmp = tmp->next; } count -= n + 1; if (count < 0) return head->next; tmp = head; while (count > 0) { tmp = tmp->next; count--; } if (NULL != tmp->next) tmp->next = tmp->next->next; return head; }};Solution 2，遍历一次链表
class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { int count = 0; ListNode* tmp = head; while (NULL != tmp) { count++; tmp = tmp->next; } count -= n + 1; if (count < 0) return head->next; tmp = head; while (count > 0) { tmp = tmp->next; count--; } if (NULL != tmp->next) tmp->next = tmp->next->next; return head; }};新闻热点
疑难解答
