单向链表 反转（单向链表反转的时间复杂度是）



题目

继续看一个来自《剑指 Offer》的链表题：

给定单向链表的头指针和结点指针，定义一个函数在 O(1) 时间内删除该结点。

我们知道，单向链表删除一个结点，通常的做法是从链表的头结点开始，顺序查找所有结点，直到找到要删除的结点并删除，因此，长度为 n 的链表删除结点的整体时间复杂度是 O(n)，但是题目要求时间复杂度为 O(1)，该怎么实现呢？在继续往下看之前，你不妨先想一想，看看有没有思路。

如果你对单向链表的概念不太熟悉，可以翻到前面的去复习下。

核心思路

按照传统的思路，删除一个单链表的时间复杂度是 O(n)，之所以要从头指针开始遍历，是为了找到被删除结点的前驱结点，然后将前驱结点的指针指向被删除结点的下一个结点，从而完成删除结点的工作。

但是细想一下，这个时间复杂度是可以优化的，在这个题目中，我们已经知道被删除结点的信息，这样就可以获知被删除结点的下一个结点，要完成删除工作，只需要把下一个结点的值复制到待删除结点，然后把待删除结点的指针指向下一个结点指针指向的结点，这样一来，也就达成了删除待删除结点的目的，这个思路是不是很巧妙？

其实，这个思路在前面介绍的时候也用到过，知识积累到一定程度，都是触类旁通的。

显然，这种只需要获取待删除结点的下一个结点的时间复杂度是 O(1)。不过我们考虑问题还要全面：如果待删除结点是头结点或者中间结点，存在下一个结点的情况下可以这么做；如果待删除结点是尾结点，没有下一个结点呢？这个时候还是要按照遍历所有结点的思路找到前驱结点来做。在这种极端情况下，时间复杂度仍然是 O(n)，不过这只是极端特殊情况，就整体平均而言，时间复杂度就是 O(1)。

实现代码

有了上面的思路，写起实现代码来也就简单了。为了提升代码复用率，我们将中编写的单链表节点类和遍历方法抽取到独立的 Go 文件 ：

然后在同级目录下创建一个 定义结点删除方法：

最后编写一段测试代码，验证删除结点是否成功：

执行测试代码，打印结果如下，表明删除成功：

（本文完）

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/19854.html