Description
Given a linked list, remove the n-th node from the end of list and return its head.
给定一个链表，删除链表中倒数第n个节点，返回链表的头节点。
Note: Given n will always be valid.
Examples
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.
Answer
Use two pointers. One is n step further than another one and then two pointers move together until the fast one reaches the end. Then the slow pointer is pointing to the node needs to be deleted.
Time Complexity
O(n)
Code
C++
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* res = new ListNode(0);
res->next = head;
ListNode* tmp = res;
for(int i = 0; i < n; ++i)
head = head->next;
while(head)
{
head = head->next;
tmp = tmp->next;
}
tmp->next = tmp->next->next;
return res->next;
}
};
