算法-O(1)时间删除链表的指定结点

题目:给定一个链表的头指针和一个结点的指针,定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下:

struct ListNode
{
  int value;
  ListNode *next;
};
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted);

解题思路: 首先,乍一看这个名字而不看题目要求的话,这是功能是不可能在O(1)时间完成的,我们在之前讨论过关于单链表插入与删除的问题,链表的性质决定了不可能在O(1)下完成。所以题目给了我们其他的内容:要删除的结点的指针

那么按照之前单链表删除的思想来考虑的话,可以完成这件事,假设要删除的结点为i,i的前一个结点为h,那么我们需要找到h,并把h的next指针变为i的next指针,并释放i。

h->next = i->next;
free(i);

这样的话i就删除了,不贴图了,前面的博客都有。但是这个思路不满足题目要求,因为单链表只有一个指向next的指针,那么我们想找到h只能从头遍历,一旦出现遍历这个东西,显然时间复杂度就不会是O(1)。

那么借助i前面的结点h是不行了,我们可以考虑能不能借助i后面的结点j,因为链表找到后面的结点只需要一步。我们只需要把j的value赋值给i的value,那么问题就变得清晰了: 要删除的结点变成了j,而i就是j前面的一个结点,而i是题目给的,不需要遍历得到。我们把问题从删除i找h,变换到了删除j找i上。

但是仅仅上面的内容还不够全面,因为我们利用了i的下一个结点j完成这个任务,但是如果i是尾结点呢? 这时我们还需要借助i的前一个结点h这种方法,即让h的next为null,并释放i。 那么这样来看的话,又有了一个问题,i如果没有h也没有j呢?显然链表只有一个结点,而这个结点就是要删除的那个。

代码实现

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if(!pListHead || !pToBeDeleted)
        return;

    // 要删除的结点不是最后一个结点
    if(pToBeDeleted->next != NULL)
    {
        ListNode* pNext = pToBeDeleted->next;
        pToBeDeleted->value = pNext->value;
        pToBeDeleted->next = pNext->next;

        delete pNext;
        pNext = NULL;
    }
    // 链表只有一个结点,该结点就是要删除的结点
    else if(*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
    }
    // 链表有多个结点,要删除的结点是最后一个结点
    else
    {
        ListNode* pNode = *pListHead;
        while(pNode->next != pToBeDeleted)
        {
            pNode = pNode->next;            
        }
        pNode->next = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

最后我们需要有两个注意的方法: (1)这种方法有一个假设条件,那就是i确实出现在链表中。 (2)代码中还是出现了循环while,但是好在这个while在if里面,也就是遍历是有条件的,这个条件就是一个长度是n的链表,要删除的结点是尾结点,这个概率是1/n。除了这个之外,代码中其他部分的时间复杂度都是O(1),所以平均来看的话,整体的时间复杂度满足O(1)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

1656
来自专栏mySoul

​单链表 C++

772
来自专栏LeetCode

LeetCode 114. Flatten Binary Tree to Linked List

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

150
来自专栏LeetCode

LeetCode 543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree....

830
来自专栏大闲人柴毛毛

剑指offer——快速排序

        快速排序是目前所有排序中性能较好的一种算法,最好情况和平均情况下时间复杂度均为O(nlogn),最坏的情况下时间复杂度为O(n^2)。快速排序采...

3477
来自专栏书山有路勤为径

移除K个数字

LeetCode 402. Remove K Digits 已知一个使用字符串表示的非负整数num,将num中的k个数字移除, 求移除k个数字后,可以获得的...

823
来自专栏vue学习

JS数据结构与算法-二叉树和二叉查找树

①先递归遍历左子树到尽头,将每一项push到一个数组中,先是得到这样的一个结果[56,22,10]。

703
来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

3016
来自专栏大数据学习笔记

面试算法题

题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中,每一行都按...

9286
来自专栏开发与安全

数据结构:线性表之顺序存储结构

线性表的数据对象集合为 {a1,a2,....an},每个元素的类型均为Datatype。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后...

1788

扫码关注云+社区