LeetCode之“链表”：Remove Nth Node From End of List

　　题目要求：

　　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.

　　这道题比较常规的想法是先算出链表长度len，再将头指针移动len-n步就可以到达待删节点了。具体程序如下（4ms）：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* removeNthFromEnd(ListNode* head, int n) {
12         if(!head)
13             return head;
14         
15         int len = 0;
16         ListNode *start = head;
17         while(start)
18         {
19             len++;
20             start = start->next;
21         }
22         
23         if(len == n)
24         {
25             start = head;
26             head = head->next;
27             delete start;
28             start = nullptr;
29             return head;
30         }
31         
32         ListNode *preNode = head;
33         start = preNode->next;
34         int k = 1;
35         while(k < len - n)
36         {
37             preNode = start;
38             start = start->next;
39             k++;
40         }
41         
42         preNode->next = start->next;
43         delete start;
44         start = nullptr;
45         
46         return head;
47     }
48 };

　　另一个比较巧妙的方法就是先定义一个慢指针（初始值为头指针父指针），让头指针移动n步，再让头指针和一个慢指针同时移动直至头指针为空，这时慢指针指向的下一个节点就是待删节点。具体程序日如下（4ms）：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* removeNthFromEnd(ListNode* head, int n) {
12         if(!head)
13             return head;
14         
15         ListNode *dummy = new(nothrow) ListNode(INT_MIN);
16         assert(dummy);
17         dummy->next = head;
18         
19         for(int i = 0; i < n; i++)
20             head = head->next;
21         
22         ListNode *preNode = dummy;
23         while(head)
24         {
25             head = head->next;
26             preNode = preNode->next;
27         }
28         
29         ListNode *delNode = preNode->next;
30         preNode->next = delNode->next;
31         delete delNode;
32         delNode = nullptr;
33         
34         head = dummy->next;
35         delete dummy;
36         dummy = nullptr;
37         
38         return head;
39     }
40 };