[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.

思路：

终于开始扫linked list的题目了。linked list题目大多不是特别难，但是写对又往往不容易。一些容易犯的错误是：

1. 越界：容易造成内存访问错误，比如调用了NULL->next。尤其对于空链表的特殊情况。

2. 更新head的特殊处理

3. 删除节点时没有保留下一个移动位置的指针（多用于reverse linked list）。

4. 移动位置存在+-1的偏差。 

5. 链表题多用指针操作。注意指针作为函数参数时是pass by value： f(ListNode *p)，还是pass by reference：f(ListNode *&p)

常用技巧：
1. Dummy head：简化改变、删除头指针的处理。
2. 前后双指针：多用于链表反转。

所以做这类题目时，一定要在纸上画图。写完代码后必须要跑test case来确认正确。

这是一道简单题，两个关键点：

1. 找到倒数第n+1个节点。

2. 通过找到的节点来删除倒数第i个节点。

如何找到倒数第k个节点?双指针before, after。让before先从head开始走k步，然后双指针同时走，当before为NULL时，after所指的就是倒数第k个节点。以题中例子说明：

k=2

1->2->3->4->5->NULL

 |          |

after   before

1->2->3->4->5->NULL

                  |           |

                after      before

需要注意的corner case （尽管LeetCode的test case中n总是小于等于链表长度）

1. k<1

2. k>链表长度，当before从head移动i<k步就已经指向NULL。而如果正好移动k步指向NULL，则k即为链表长度。

3. 要删除的节点为头节点，对应k=链表长度。判断条件在2中已说明。

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

class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { if(n<1) return head; int i=0; ListNode *before=head; while(i<n+1 && before) { before = before->next; i++; } if(i==n+1) { ListNode *after = head; while(before) { before = before->next; after = after->next; } ListNode* temp = after->next; after->next = temp->next; delete temp; } else if(i==n) { // remove head ListNode *temp = head; head = head->next; delete temp; } return head; } };