文档章节

203. Remove Linked List Elements

cofama
 cofama
发布于 2017/02/23 23:02
字数 698
阅读 7
收藏 0

 原题链接https://leetcode.com/problems/remove-linked-list-elements/?tab=Description

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

       这题考的是链表操作,毫无疑问要用指针遍历链表的每一个元素。removeElements函数头中给出的参数head应该是指向链表首元素的指针,那么就可以采用head=head->next的方法移动指针遍历。这样我就有两种思路:一,用一个指针nextNode指向当前项的下一项,判断nextNode->val是否等于val,是的话就“跳过”这一项,即把当前元素的next指针改为指向下下个元素。二,新建一个lastNode指针作为“伪首元素”,它的next指向真正的链表首元素(也是head初始指向的地方),判断head->val是否等于val,是的话就“跳过”head指向的当前项,把lastNode的next指向当前项的下一项,不是的话就要用lastNode=lastNode->next移动指针,确保lastNode永远指向当前项的前一项。经过思考我决定采用第二种方法,因为第一种有一个问题,就是用nextNode的话无法判断首元素是否等于val,而且当链表只有一个元素时会出现问题。C++代码如下:

/**
 * 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) {
        ListNode* lastNode = new ListNode(0);
        lastNode->next = head;
        ListNode* first = lastNode;
        while(head != NULL) {
        	if(head->val == val) {	
        		lastNode->next = head->next;
			}
			else lastNode = lastNode->next;
			head = head->next;
		}
		//delete lastNode;
        //lastNode = NULL;
		first = first->next;
		return first;
    }
};

      创建lastNode指针时使用的参数0没有特殊意义,只是为了满足构造函数。first指针用于保存伪首元素,因为lastNode后面是会移动的,函数最后返回的是伪首元素的next指针,也就是指向首元素。这段代码里有一句注释掉的delete语句,我原本是想释放lastNode使用的内存空间,但是会报一个runtime error:double free and corruption,double free的意思是重复释放内存。而且经过测试发现,是因为执行了lastNode=lastNode->next才导致error。这篇博文http://blog.csdn.net/hazir/article/details/21413833有介绍delete的作用是释放指针指向的对象使用的内存,但指针本身的内存不会释放,也就是说我的这个delete语句其实是释放了链表中的一个listNode元素,所以这个做法本身是有问题的,但我还是没看出来哪里有“重复释放内存”,因为我应该只用了一次delete(http://www.cnblogs.com/laipDIDI/articles/2173532.html有介绍几种不正确delete导致的错误)。哪位大神路过的话帮忙解答一下。

© 著作权归作者所有

共有 人打赏支持
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员

暂无文章

深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
11分钟前
0
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
44分钟前
0
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
0
0
openJDK之sun.misc.Unsafe类CAS底层实现

注:这篇文章参考了https://www.cnblogs.com/snowater/p/8303698.html 1.sun.misc.Unsafe中CAS方法 在sun.misc.Unsafe中CAS方法如下: compareAndSwapObject(java.lang.Object arg0, long a......

汉斯-冯-拉特
今天
2
0
设计模式之五 责任链模式(Chain of Responsibility)

一. 场景 相信我们都有过这样的经历; 我们去职能部门办理一个事情,先去了A部门,到了地方被告知这件事情由B部门处理; 当我们到了B部门的时候,又被告知这件事情已经移交给了C部门处理; ...

JackieRiver
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部