Google+ Followers

Sunday, December 30, 2012

[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.
» 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:    }  


Post a Comment