您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

力扣每日一题之移除链表元素

题目描述

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

算法思路

递归

迭代

迭代是比较容易想到的 但是这里卡了我很久都没能实现解题(逻辑比较复杂)

根据官方题解做的
这是代码行数最少、最优美的(迭代法中)
相当于在前驱指针的基础上 利用链表的特性做了指针的偏移,在操作过程中可以少写一个指针。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy = ListNode(-1,head);//虚拟节点
        ListNode* curr = &dummy;
   
        while(curr->next!=nullptr)
        {
            if(curr->next->val==val)
            {
                curr->next=curr->next->next;
            }

        else curr=curr->next;
        }
        return dummy.next;

    }
};

最终确定为两个问题:
1.首先头结点也可能被删除,所以需要虚拟头结点(哑节点)
2.直接操作过程中 可以轻易删除下一个节点,比较难删除当前节点。

删除下一个节点的方法是node.next=node.next.next;

在题解中看到一个解法:就是纯暴力法,没有在这两个问题上做优化

作者:traveller-lzx
//删除链表元素
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return NULL; //为空直接返回
        ListNode * pre = NULL; //前驱指针
        ListNode * p = head ; //工作指针
        while(p){ //如果p不空
            if(p->val==val){ //找到删除元素
                if(pre==NULL){ //如果前驱是空的,说明链表第一个元素就是要删除的
                    p = p->next; //直接让p指向下一个
                    pre = NULL; //前驱依旧指向空
                }
                else{
                    pre->next = p->next; //从中间断开连接
                    p = p->next; //更新p指针,pre不用更新;
                }
            }//如果不是被删除元素
            else{
                if(pre==NULL&&p!=NULL) head = p; //如果pre为空,p不空,说明现在是新链表的头,更新链表头指针
                pre = p; //更新前驱指针
                p = p->next; //更新工作指针
            }
        }
        if(pre==NULL&&p==NULL){ //如果发现前驱pre和p都为空,说明整个链表都被删了
            return NULL;
        }
        else{
            return head;
        }
    }
};

作者:traveller-lzx
链接:https://leetcode-cn.com/problems/remove-linked-list-elements/solution/yi-chu-lian-biao-yuan-su-die-dai-by-trav-29s1/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

在他的基础上我做了一些优化

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
	ListNode* curr=head;//工作指针,一般不要直接操作源指针
	ListNode* prev=nullptr;//前一个节点指针(前驱指针)
	
	while(curr!=nullptr)//遍历链表
	{
		if(curr->val==val)//当前节点需要被删除
		{
			//如果你需要删除当前节点,得有前一个节点
			//若前一个节点是空,则说明为头结点
			if(prev==nullptr)//判断是否为头结点
			{
			//需要直接更换链表头
			head = curr->next;
			}
			else//不是头结点
			{
			prev->next=curr->next;//删除当前节点
			}
			curr=curr->next;//更新(迭代)工作指针
		}
		else//当前节点不需要被删除
		{
		prev=curr;
        curr=curr->next;//正常迭代更新
		}
	}
	return head;
    }
};

然后又引入了哑结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy = ListNode(-1,head);//虚拟节点
        ListNode* prev = &dummy;//前驱指针
        ListNode* curr = &dummy;//工作指针
   
        while(curr!=nullptr)
        {
            if(curr->val==val)//找到需要被删除的结点
            {
                prev->next=curr->next;//删除当前节点
                curr=curr->next;//只更新工作指针
            }

            else 
            {
                prev=curr;
                curr=curr->next;//正常迭代更新
            }
        }
        return dummy.next;

    }
};

题目标签

递归、链表

刷题总结

对链表有了新的认识 特别有意思,也特别难
一些比较需要重点关注的点:
1.迭代思想 迭代到底是什么
2.哑结点思想
3.前驱指针、工作指针的概念以及使用
4.直接做偏移利用链表中的next指针,直接判断下一个,不判断当前。

链表还得再练 概念比较抽象
而且之前使用得少 最好先把b站的那几P看完

下题规划

  • 本题的递归做法
  • 力扣237
  • 力扣705
  • 力扣706

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进