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

» Solve this problem

[解题思路]
经典题。双指针，一个指针先走n步，然后两个同步走，直到第一个走到终点，第二个指针就是需要删除的节点。唯一要注意的就是头节点的处理，比如，
1->2->NULL, n =2; 这时，要删除的就是头节点。


[Code]

1:    ListNode *removeNthFromEnd(ListNode *head, int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      assert(head);  
5:      ListNode* pre, *cur;  
6:      pre = head;cur = head;  
7:      int step = 0;  
8:      while(step< n && cur!=NULL)  
9:      {  
10:        cur = cur->next;  
11:        step++;  
12:      }  
13:      if(step ==n && cur == NULL)  
14:      {  
15:        head = head->next;  
16:        delete pre;  
17:        return head;  
18:      }  
19:      while(cur->next!=NULL)  
20:      {  
21:        pre = pre->next;  
22:        cur = cur->next;  
23:      }  
24:      ListNode* temp = pre->next;  
25:      pre->next = temp->next;  
26:      delete temp;      
27:      return head;  
28:    }