明港网站建设,网站模板 手机app展示,合同网站开发 设计 后期维护,电商网站建设基础ppt目录
题目#xff1a;
示例;
分析:
代码: 题目#xff1a; 示例; 分析:
给我们一个链表#xff0c;让我们把链表中间的节点删了。
那么最直观最基础的办法是遍历两边链表#xff0c;第一遍拿到链表长度#xff0c;第二次把链表中间节点删了。
这个暴力做法我没事过…目录
题目
示例;
分析:
代码: 题目 示例; 分析:
给我们一个链表让我们把链表中间的节点删了。
那么最直观最基础的办法是遍历两边链表第一遍拿到链表长度第二次把链表中间节点删了。
这个暴力做法我没事过不过貌似是可以解决问题的所以我觉得这题的难度不能算是中等。
那除了这个暴力解法有没有其他办法解决问题呢其实是有的。
我们之前每日一题有做过类似的链表题是检测一个链表是否是环形链表。
【力扣每日一题】2023.7.29 环形链表_折途的博客-CSDN博客其实这是很经典的快慢指针题。我们需要定义两个指针来遍历这个链表其中一个快指针比慢指针每次多走一次如果快指针走到了链表末尾那么就没有环。如果链表有环那么因为快指针移动比慢指针多因此他们最终会相遇快慢指针相遇则表示链表有环。题目给我们一个链表让我们判断这个链表是否有环。我们可以直接遍历这个链表最后能走到链表末尾也就是空指针那就代表这个链表没有环如果一直死循环在走那么就说明我们陷入环了。当然我们不可能这么做不可能每次判断一个链表有概率让我们的程序陷入死循环那么我们应该怎么做呢。https://blog.csdn.net/m0_63235356/article/details/131991214?spm1001.2014.3001.5502然后我们用的方法是快慢指针我们知道快指针走的路是慢指针的两倍因此如果快指针走到了链表末尾那么慢指针所在的位置就是链表的正中间。
然后我们再将当前慢指针所指的节点删除即可。为了实现删除节点的效果我们让慢指针的上一个节点的后驱指向慢指针的下一个节点直接跳过慢指针就达到了删除指针的效果。
所以我们还要额外定义一个指针用于记录慢指针的上一个节点。 代码:
class Solution {
public:ListNode* deleteMiddle(ListNode* head) {//定义快慢指针,快指针每次走两格,慢指针一次走一格ListNode* fasthead;ListNode* curhead;ListNode* prenullptr; //定义一个前驱节点,用于删除中间节点if(fast-nextnullptr) return pre;//快指针走到尽头则表示当前的慢指针在中间节点位置,开始删除while(fast!nullptr fast-next!nullptr){ fastfast-next-next;precur;curcur-next;}pre-nextcur-next; //跳过前驱节点的下一个节点达到删除节点的效果.return head; }
};
