## Wednesday, November 19, 2014

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

1. 越界：容易造成内存访问错误，比如调用了NULL->next。尤其对于空链表的特殊情况。
4. 移动位置存在+-1的偏差。
5. 链表题多用指针操作。注意指针作为函数参数时是pass by value： f(ListNode *p)，还是pass by reference：f(ListNode *&p)

2. 前后双指针：多用于链表反转。

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

k=2

1->2->3->4->5->NULL
|          |
after   before

1->2->3->4->5->NULL
|           |
after      before

1. k<1
 ``` 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(inext; 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; } }; ```