# 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

1.Try two pointers.

2.Did you use the property of “the order of elements can be changed”?

3.What happens when the elements to remove are rare?

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int new_len=0,i=0,size=nums.size();
for(i=0;i<nums.size();i++){
if(nums[i]!=val){
nums[new_len++]=nums[i];
}
}
return new_len;
}
};


class Solution {
public:
int removeElement(vector<int>& nums, int val) {
return distance(nums.begin(),remove(nums.begin(),nums.end(),val));
}
};


# 203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example

Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6

Return: 1 –> 2 –> 3 –> 4 –> 5

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
struct ListNode dummy(0);
struct ListNode *pmove=&dummy;
while(pmove->next){
if(pmove->next->val==val)
pmove->next=pmove->next->next;
else
pmove=pmove->next;
}
return dummy.next;
}
};


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

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
struct ListNode dummy(0);
struct ListNode * fast=&dummy,*slow=&dummy,*tmp=NULL;
for(int i=n;i>0;i--)
fast=fast->next;
while(fast->next){
fast=fast->next;
slow=slow->next;
}
tmp=slow->next;
slow->next=tmp->next;
delete tmp;
return dummy.next;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017