刚看到题目的想法是使用两次遍历,第一次确定该链表的长度,再减去n,进行第二次遍历,从而删除对应位置的元素。
因此,可以使用双指针来实现,第一个指针先移动n+1位,第二个指针再从头移动,当第一个指针到达结尾时,第二个指针的下一个元素便是需要删除的元素
1 ListNode* removeNthFromEnd(ListNode* head, int n) { 2 3 if(n==0)return head; 4 ListNode *p=head; 5 ListNode *q=head; 6 for(int i=0;i<n+1;i++){ 7 if(q) 8 q=q->next; 9 else return head->next;//如果q直到末位循环还未结束,说明n=链表长度(题目说明了n是有效的)。其需要删除第一个元素 10 } 11 while(q){ 12 p=p->next; 13 q=q->next; 14 } 15 ListNode *s=p->next; 16 p->next=s->next; 17 delete s; 18 return head; 19 }
写完以后发现执行时间12ms,o(╥﹏╥)o
就去看了看0ms的代码,和我的思路一样,不同的地方在于,其在开始建立一个空的头结点,放在head的前面
1 ListNode dummy = new ListNode(0); 2 dummy.next = head;
此题也是采用双指针的方式,刚开始陷入一个错误的思路:就是两个指针同时移动,一个前i一个后j,一旦发现前指针i和该指针前面i-1的一样,就把后指针j赋值给前指针i。(这种做法仅仅是将数据往前移动,并未消除重复项)(傻傻的做法)
而应当前指针i只有在后指针发现和i不同的元素以后再往后移动,并进行赋值操作。
1 int removeDuplicates(vector<int>& nums) { 2 int i=0; 3 int j=1; 4 if(nums.size()==0)return 0;//如果vector为空 5 // if(nums.size()==1)return 1; 6 while(j<nums.size()){ 7 if(nums[i]==nums[j]){//当两指针的值相等时,i不移动 8 j++; 9 } 10 else{ 11 i++;//i往后移动一位 12 nums[i]=nums[j];//将第一个与i-1不同的数字赋值给i 13 j++; 14 } 15 } 16 return i+1; 17 18 }
这题和前面那题十分相似,几乎可以是同一种方法
1 int removeElement(vector<int>& nums, int val) { 2 int i=0,j=0; 3 int m=0; 4 while(j<nums.size()&&i<nums.size()){ 5 if(nums[i]!=val){ 6 i++;m++;//m用于记录元素个数 7 } 8 else{ 9 j=i+1; 10 while(j<nums.size()){ 11 if(nums[j]!=val) {nums[i]=nums[j];nums[j]=val;break;} 12 j++; 13 } 14 } 15 } 16 return m; 17 }
在官方解法中只使用了一次遍历,并对其进行了优化!
原文:https://www.cnblogs.com/liujiuba/p/12861146.html