移除链表元素详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了移除链表元素详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原题出处：. - 力扣（LeetCode）

方法一：迭代

我们可以新创建一个链表，然后将不等于val的节点拿下来进行尾插，这样的方式更加简易，只需要遍历整个链表即可。

我们首先使用一个指针cur来遍历原链表，来获取不等于val的节点。

如果cur的next等于val就跳过这个节点，如果不等于val就尾插，直到当cur等于NULL,这时候就遍历完了整个数组。

然后再使用两个指针分别指向新链表的开头和末尾。

移除链表元素详解,刷题,链表,数据结构

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* newhead = NULL,*newtail = NULL,*cur = head;
	while(cur != NULL) {
		if (cur->val != val) { 
			if (newhead == NULL) {
				newhead = newtail =  cur;
			}
			else {
				newtail->next = cur;
                newtail = newtail->next;
			}
		}
		cur = cur->next;
	}
    if(newtail)
        newtail->next = NULL;
	return newhead;
}

最开始进行尾插的时候，因为newhead和newtail都是NULL,这时候并不是尾插而是让newhead和newtail指向这个节点。

为了避免这个情况，我们也可以使用带有哨兵位的链表来解决这个问题。

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* guardHead = malloc(sizeof(struct ListNode));
	guardHead->next = head;
	struct ListNode* cur = guardHead;
	while (cur->next != NULL) {
		if (cur->next->val == val) {
			cur->next = cur->next->next;
		}
		else {
			cur = cur->next;
		}
	}
	struct ListNode* ret = guardHead->next;
	free(guardHead);
	return ret;
}

但是由于这个哨兵位是我们malloc的，最后离开函数一定要释放，否则会造成内存泄漏。

这个方法是有点缺陷的，如果这些节点是使用动态内存开辟的，我们就没有释放这些节点，但是这个方法是满足题目条件的。

方法二：递归

链表的定义是具有递归的性质，因此链表的题目是可以使用递归解决的

首先我们明白这个函数的功能是删除这个链表中等于val的元素的，那么我们可以对除开第一个节点的对后面的节点使用这个函数，得到的返回值就是就是后面的所有的节点就没有等于val的了。

    head->next = removeElements(head->next,val);

这样我们head->next后面的节点都没有了等于val的。

然后由于我们没有判断第一个节点是否等于val，此时我们就可以使用三目操作符来判断了。

 return head->val == val ? head->next : head;

如果头节点是等于val的，我们就返回head->next,这样我们就删除了所有等于val的节点。如果不等于val就直接返回head即可。

但是这里还有一个问题就是如果head节点是空，这样就会非法访问空节点了，所有我们还要判断是否是空节点。

struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head == NULL){
        return head;
    }
    head->next = removeElements(head->next,val);
    return head->val == val ? head->next : head;
}

文章来源地址https://www.toymoban.com/news/detail-858266.html

到了这里，关于移除链表元素详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！