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