Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

Have you met this question in a real interview? 

Yes

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

Note

The minimum number of nodes in list is n.

Challenge

O(n) time

一道基础题，不过用了两个linkedlist常用的技巧： dummy node和快慢指针 （算是吧。。。）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @param n: An integer. * @return: The head of linked list. */ ListNode *removeNthFromEnd(ListNode *head, int n) { // write your code here ListNode dummy(0); dummy.next=head; head=&dummy; for (int i=0; i<n; i++){ if (!head->next) return 0; head=head->next; } ListNode* prev=&dummy; while(head->next){ prev=prev->next; head=head->next; } ListNode* tmp= prev->next; prev->next= prev->next->next; delete tmp; return dummy.next } };