Remove Nth Node From End of List

**一. 题目描述** Given a linked list, remove the n th 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`的值默认是合法的。不过其实对输入的n进行异常判断也只需要几句语句。 使用两个指针，即快/慢指针的概念，其中一个指针先走`n`步，然后慢指针走，等到快指针走到结尾时，那么慢指针走到了需要删除的节点的**前一个位置**。 这道题主要难点是考虑边界问题，以及特殊情况（要删除的是头节点），如输入`1->2->3->4`， `n=4`，那么需要删除`1`，此时只需将头指针`head = head->next`就可以了。 **三. 示例代码** ~~~ #include struct ListNode { int value; ListNode* next; ListNode(int x): value(x), next(NULL){}; }; class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { if (head == NULL) return NULL; ListNode *fast = head; ListNode *slow = head; ListNode *temp = head; for (int i = 0; i < n ; i++) { fast = fast->next; if (fast) continue; else break; } while (fast) { fast = fast->next; temp = slow; slow = slow->next; } if (slow == head) { head = head->next; return head; } temp->next = slow->next; delete slow; return head; } }; ~~~ 结果：    **四. 小结** 实际编程中经常会遇到边界问题，不小心的错误很容易造成程序奔溃，关于指针和链表的使用技巧还需要进一步的学习。