【面试题】剑指offer13--在O(1)时间删除链表结点

末蓝、 2022-06-12 23:39 106阅读 0赞

删除链表的节点有很多的方法，有普通的和简单的

由于函数需要传入头结点和删除的节点，我们可以将删除节点Del的下一个节点Next删除

在删除前，将Next节点的值赋值给Del，间接的实现了删除

注意：如果删除的情况是尾节点（Del->m\_pnext == NULL），则还需要从头遍历进行删除

综合情况下，该[算法][Link 1]的时间复杂度为O(1)

代码的实现：

#include<iostream>
    using namespace std;
    struct ListNode
    {
    	int _value;
    	ListNode* next;
    };
    void DeleteNode(ListNode** pListHead, ListNode* pToBeDelete)
    {
    	if (!pListHead || !pToBeDelete)//如果头结点为空或者将要删除的节点为空，就返回
    	{
    		return;
    	}
    	if (pToBeDelete->next != NULL)
    	{
    		ListNode* pNext = pToBeDelete->next;
    		pToBeDelete->_value = pNext->_value;
    		pToBeDelete->next = pNext->next;
    		delete pNext;
    		pNext = NULL;
    	}
    	else if (*pListHead == pToBeDelete)
    	{
    		delete pToBeDelete;
    		pToBeDelete = NULL;
    		*pListHead = NULL;
    	}
    	else
    	{
    		ListNode* pNode = *pListHead;
    		while (pNode->next != pToBeDelete)
    		{
    			pNode = pNode->next;
    		}
    		pNode->next = NULL;
    		delete pToBeDelete;
    		pToBeDelete = NULL;
    	}
    }

[Link 1]: http://lib.csdn.net/base/datastructure

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 AcWing 28. 在O(1)时间删除链表结点（C++）- 链表

题目链接：[https://www.acwing.com/problem/content/85/][https_www.acwing.com_problem_content_8

曾经终败给现在/ 2022年08月28日 04:40/ 0 赞/ 102 阅读

相关剑指offer之面试题13在O(1)时间删除链表结点

问题描述：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间内删除该结点。结构题如下： struct ListNode{ int val

ゞ浴缸里的玫瑰/ 2022年08月22日 03:47/ 0 赞/ 92 阅读

相关剑指Offer面试题13（java版）:在O(1)时间删除链表节点

题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。在单向链表中删除一个节点，最常规的方法无疑是从链表的头结点开始，顺序遍历查找要删除的节点，并

Myth丶恋晨/ 2022年07月16日 04:54/ 0 赞/ 122 阅读

相关【面试题】剑指offer13--在O(1)时间删除链表结点

删除链表的节点有很多的方法，有普通的和简单的由于函数需要传入头结点和删除的节点，我们可以将删除节点Del的下一个节点Next删除在删除前，将Next节点的值赋值给Del

末蓝、/ 2022年06月12日 23:39/ 0 赞/ 107 阅读

相关剑指offer面试题[57]-删除链表中重复的结点

题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1

素颜马尾好姑娘i/ 2022年06月11日 01:52/ 0 赞/ 137 阅读

相关《剑指offer》刷题笔记（代码完整性）：在O(1)时间删除链表结点

《剑指offer》刷题笔记（代码完整性）：在O(1)时间删除链表结点 -------------------- 转载请注明作者和出处：[http://blog.c

素颜马尾好姑娘i/ 2022年06月07日 03:58/ 0 赞/ 112 阅读

相关剑指offer-题57：删除链表中重复的结点

题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1

今天药忘吃喽~/ 2022年05月26日 00:53/ 0 赞/ 176 阅读

相关在O(1)时间删除链表结点——面试题13《剑指offer》

题目：给定单向链表得头指针和一个节点指针，定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下： struct ListNode {

分手后的思念是犯贱/ 2022年05月10日 12:36/ 0 赞/ 125 阅读

相关【剑指Offer】（链表）删除链表中重复的结点

题目链接：[https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11

蔚落/ 2022年03月17日 14:28/ 0 赞/ 221 阅读

相关《剑指offer刷题笔记》16、在O(1)时间删除链表结点【c++详细题解】

题目给定单向链表的一个节点指针，定义一个函数在 O ( 1 ) O(1) O(1)时间删除该结点。假设链表一定存在，并且该节点一定不是尾节点。样例

川长思鸟来/ 2021年07月24日 11:31/ 0 赞/ 255 阅读