LeetCode 19. Remove Nth Node From End of List（medium难度）

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个节点，由于n是有效的，所以暂时可以不考虑关于n的异常值。这一点我还是想多说一句，leetcode更专注于问题本身的解决，而《剑指offer》则更关注于解决问题的同时让程序更加健壮。

这道题最直接的思路是先遍历一遍链表，得到链表的长度L，倒数第n个，其实就是正数L-n+1个，然后正向遍历删除该节点即可。但是这么做需要遍历链表2遍，其实可以进一步改进，我们考虑如何只遍历链表一遍。这里不妨考虑设置2个指针，最开始两个指针都指向head，第一个指针cur先走n步，然后两个指针一起走，当cur的next为null，pre指向的是待删除节点的前一个节点，我们直接通过指针把该节点的下一个节点（也就是倒数第n个节点）删除即可，代码如下：

 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 {
11 public:
12     ListNode* removeNthFromEnd(ListNode* head, int n) 
13     {
14         //题目中已经说了n一定有效，那么暂时不考虑各种异常输入
15         if (!head || !head->next)
16             return nullptr;
17         ListNode *cur = head, *pre = head;
18         for (int i = 0; i < n; i++)
19             cur = cur->next;
20         if (!cur)    //这里一定小心，我之前不小心写成了cur->next
21             return head->next;
22         while (cur->next)
23         {
24             pre = pre->next;
25             cur = cur->next;
26         }
27         pre->next = pre->next->next;
28         return head;
29     }
30 };

时间复杂度：O(n)

空间复杂度：O(1)