优秀英文企业网站,南宁seo网络优化公司,哪个网站做衣服的,帝国网站认证码目录 申明
题目
分析题目信息
解题思路
代码解析
技巧解析#xff1a;创建虚拟头结点
时间复杂度分析
思考#xff1a;能否只用一趟扫描实现#xff1f;
双指针
双指针解题思路
代码解析 申明 该题源自力扣题库19#xff0c;文章内容#xff08;代码#xff0c…目录 申明
题目
分析题目信息
解题思路
代码解析
技巧解析创建虚拟头结点
时间复杂度分析
思考能否只用一趟扫描实现
双指针
双指针解题思路
代码解析 申明 该题源自力扣题库19文章内容代码图表等均原创侵删
题目 给你一个链表删除链表的倒数第n个结点并返回链表
示例n2删除倒数第二个链表。 输入[1,2,3,4,5]
输出[1,2,3,5]
链表结构体
struct ListNode {int val;struct ListNode *next;
};题目相关信息到此为止我们需要分析一下题目。
回顾链表结点的删除最重要的步骤是找到要被删除的结点的前驱结点修改其next指向要被删除结点的后继结点。例如例题中的要被删除结点为4因此要将其前驱结点3指向其后继结点5.
分析题目信息
其次观察题目我们可以获得一些信息
该链表为无头结点的单链表因此删除过程中需要注意第一个结点的删除与其他结点有些许不同。该链表删除结点位置是倒着数的但是单链表是不可逆的因此在删除时要找到需要删除的位置必须知道链表总长length然后遍历链表到length-n个位置进行删除。
解题思路
根据上述的信息我们解决该问题的大致思路是
遍历链表获取链表总长信息length找到要被删除结点的前驱结点length-n修改前驱结点的next释放要删除的结点空间
代码解析
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {int length 0;//初始化链表总长为0/*1.遍历链表获取链表总长*/struct ListNode* p ;//p表示当前结点p head;while (p! NULL) {length;p p-next;}/*为了方便删除操作我们创建一个虚拟头结点*/struct ListNode dummy;dummy.next head;struct ListNode* prev dummy;//prer表示当前结点/*2.遍历链表找到要删除结点的前驱结点*/for (int i0;i length - n;i) {prev prev-next;}/*3.修改前驱结点的next*/struct ListNode* s prev-next;//s暂存要被删除结点prev-next s-next;//修改要被删除结点的前驱结点的next指针/*4.释放要删除的结点空间*/free(s);//释放内存空间return dummy.next;//返回链表头结点
}技巧解析创建虚拟头结点
我们再来观察一下是否有头结点的链表的区别
有头结点的链表 L为头结点它和其他结点没有本质上没有区别但其本身不存储数据它的next指针指向第一个结点从第一个结点开始才算链表的真正数据主体。
无头结点的链表 这里我们需要注意这里的L不是结点只是一个指针它没有next而是直接指向第一个结点。 回顾一下链表的插入和删除非常重要的一个步骤就是修改被操作结点的前驱结点的next。 而我们在对无头结点链表的第一个结点进行操作时找不到其前驱结点因此需要对其特殊处理其处理方式和其他结点会有略微差距因此代码上较为繁杂。而有头结点的存在则不需要考虑第一个结点的问题相对来说操作更加方便逻辑更加清晰统一。 为了使代码操作更具有统一性我们可以在函数内部创建一个虚拟头结点将虚拟头指针的next指向原链表的第一个结点暂时供链表使用。在使用完成后注意输出时的结点要从虚拟头结点的next结点摒弃头结点保持输入输出链表结构的一致性。
时间复杂度分析 时间复杂度分析当数据量足够大时影响其时间的往往是最深层的代码相对而言其它层的可以忽略不记。因此上述方法的时间复杂度主要来自于两个循环语句while和for。第一个while用于遍历链表获得链表长度数据lengthfor用于找到链表中要被删除结点的前驱结点(length-n)。
最好情况是nlength要删除结点为第一个结点时间复杂度为O(1).最坏情况为n1要删除结点为最后一个结点时间复杂度为O(n).平均情况时间复杂度为O(n)
思考能否只用一趟扫描实现 不知道你们是否感觉到两次遍历很麻烦但不知道链表长度我又不知道倒数第n个在哪就很矛盾。单链表又是不可逆的不能从末尾结点去遍历这可怎么办呢到这里就陷入一个难题不找到末尾结点就找不到倒数第n个结点在哪找到末尾结点指针又在最后了单链表又不可逆又得从头遍历。好像只能遍历两遍。 我们重新审视一下这个问题
我们必须找到末尾结点以便确认倒数第n个结点的位置此时结构体指针在结尾。因为单链表不可逆我要让指针到倒数第n个结点需要重新遍历。
双指针
归根结底就是因为一个指针无法在单链表中倒着走那么我是不是可以加一个指针呢让一个指针跟在另一个指针的屁股后面距离为n。
例如 当前面那个指针指向最后一个结点时后面那个指针刚好在倒数第n个结点的前驱结点那里。
例如 这样的话就只需要遍历一次链表就能实现删除链表的倒数第n个结点
双指针解题思路
创建虚拟头结点创建前后双指针令后指针after指向头结点L前指针超过后指针n个位置前后指针同时向前直到former到最后一个结点此时after到达要被删除结点的前驱结点修改after的next释放空间
代码解析
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {/*1.创建虚拟头结点*/struct ListNode dummy;dummy.next head;/*2.创建前后双指针*/struct ListNode* former;struct ListNode* after;/*3.前后双指针位置初始化*/formerdummy;for(int i0;in;i){formerformer-next;}afterdummy;/*4.遍历链表直到former到达末尾结点*/while(former-next!NULL){afterafter-next;formerformer-next;}/*5.修改after的next*/struct ListNode* safter-next;after-nexts-next;/*6.释放空间*/free(s);return dummy.next;
}
好的各位这个题目暂时就讲到这里如果大家有新的题目或者有新的思路欢迎各位大佬评论或私信。
