侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 135 篇文章
  • 累计创建 25 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

用O(1)的时间复杂度删除链表节点

神奇的程序员
2022-02-13 / 0 评论 / 0 点赞 / 25 阅读 / 2,483 字

前言

有一个单向链表,给定了头指针和一个节点指针,如何在O(1)的时间内删除该节点?本文将分享一种实现思路来解决这个问题,欢迎各位感兴趣的开发者阅读本文。

思路分析

在单向链表中,要想删除一个节点,首先想到的做法就是:从链表的头节点开始,按照顺序遍历查找要删除的节点,找到后改变指针指向即可完成节点删除。

遍历链表,删除节点

接下来,我们举个链表的例子,删除 节点10 ,那么删除过程就如下图所示:

  • 从链表头部通过遍历的方式顺着指针进行查找
  • 发现节点9的指针指向节点10(需要删除的节点)
  • 获取节点10指针指向的节点13
  • 修改节点9的指针指向,将其指向节点13,就完成了节点10的删除

image-20220209222408426

通过这种方式,我们的确删除了给定的节点,但是需要从头开始遍历链表寻找节点,时间复杂度是O(n)。不满足题目要求,这种方式不可行。

覆盖节点,实现删除

接下来,我们换一种思路,既然最耗时的地方是遍历寻找节点,那么我们就不遍历了,充分利用题目所给条件来进一步思考。

再次审题后,我们发现它给出了要删除节点的指针,那么我们就可以拿到其指针所指向的值,有了这个值,我们就可以:

  • 将待删除节点值的进行覆盖
  • 修改指针指向,删除其下一个节点

我们继续用上个章节所举的例子,它的执行过程如下图所示:

image-20220209232658888

注意:待删除节点的下一个节点值是最后一个时,我们只需将待删除节点的指针指向null即可。

如果其下一个节点之后还有节点,那我们只需要获取那个节点,将其指针指向获取到的节点即可,如下图所示:

image-20220210213628642

通过上述思路我们在O(1)的时间内删除了给定节点,但是还有一个问题:如果要删除的节点位于链表的尾部,那么它就没有下一个节点,此时我们就不能用这个办法了,只能顺序遍历得到该节点的前序节点,并完成删除操作。

时间复杂度分析:对于n-1个非尾节点而言,我们可以在O(1)的时间内利用节点覆盖法实现删除,但是对于尾节点而言,我们仍然需要按序遍历来删除节点,时间复杂度是O(n)。那么,总的时间复杂度就为:[(n-1) * O(1) + O(n)] / n,最终结果还是 O(1),复合题目要求。

如果链表中只有一个节点,而我们又要删除链表的头节点(也是尾节点),那么,此时我们在删除节点之后还需要把链表的头节点设置为null。

实现代码

有了思路之后,我们就能愉快的写出代码了,如下所示:

  • 链表中只有1个节点时,直接返回nul,调用者删除链表的头部节点即可
  • 待删除节点无下一个节点时,则按序遍历寻找到其上一个节点,将指针指向null即可
  • 使用覆盖节点法,完成节点的删除
type ListNode = { element: number; next: ListNode | null };

export class DeleteLinkedListNode {
  deleteNode(listHead: ListNode, toBeDeleted: ListNode): ListNode | null {
    // 链表中只有一个节点时,返回null
    if (listHead.next == null) {
      return null;
    }
    // 待删除节点处于末尾时,则按顺序遍历节点实现删除
    if (toBeDeleted.next == null) {
      let curNode = listHead.next;
      // 寻找待删除节点的上一个节点
      while (
        curNode.next != null &&
        curNode.next.element !== toBeDeleted.element
      ) {
        curNode = curNode.next;
      }
      // 上一个节点已找到,将其指针指向null即可
      curNode.next = null;
      return listHead;
    }

    // 待删除节点之后还有节点,则采取覆盖法以达到删除的目的
    // 待删除节点的值改为其下一个节点的值
    toBeDeleted.element = toBeDeleted.next.element;
    // 待删除节点的指针指向待删除节点的下下个节点
    toBeDeleted.next = toBeDeleted.next.next;
    return listHead;
  }
}

测试用例

最后,我们用上个章节所举的例子来验证下代码是否能正确执行。

import { DeleteLinkedListNode } from "../DeleteLinkedListNode.ts";
import LinkedList from "../lib/LinkedList.ts";

const listNode = new LinkedList();
listNode.push(3);
listNode.push(5);
listNode.push(7);
listNode.push(9);
listNode.push(10);
listNode.push(13);
listNode.push(15);

const deleteLinkedListNode = new DeleteLinkedListNode();
// 获取链表头指针与节点10的指针
const result = deleteLinkedListNode.deleteNode(
  listNode.getHead(),
  listNode.getElementAt(4)
);
if (result == null) {
  // 删除链表的头节点
  listNode.removeAt(0);
}
console.log("删除节点10后,链表的剩余节点为:", listNode.toString());

运行结果如下所示:

image-20220213155754474

上述代码中的LinkedList类是自己实现的,对此感兴趣的开发者请移步:链表与变相链表的实现

示例代码

本文实例的完整代码如下:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
0

评论区